Как найти подстроку в потоке или в данных, которые представлены последовательностью строк?
Если данные в которых нужно найти подстроку, есть одной строкой, то это просто сделать. Есть функция $find(). А если исходные данные не могут быть представлены одной строкой, то можно применить так называемое скользящее окно и свести задачу к поиску в одной строке. Основная проблема, которую решает такой метод, состоит в поиске вхождений если искомая подстрока начинается в одном сегменте а заканчивается в другом.
Обозначим исходные сегменты:
111111
Мы можем проводить разбиение исходных данных независимо от их физического представления на сегменты с различной длиной и объединять не по два сегмента, а больше. В имплементациях mumps существуют различные ограничения на длину строки одним куском и это естественно следует учитывать. Если ограничение как в Cache, 32 килобайта, то мы можем проводить разбиение например такими способами:
M - N до M килобайт. Например, в вышеприведенном примере мы не сможем найти подстроку 12222223, хотя ее длина меньше длины конкатенации - начинается на первом, продолжается на втором и заканчивается на третьем сегменте. Собственно, этот фактор и есть основной для гарантирования поиска подстроки длиной S килобайт. Размер одного сегмента должен быть не больше чем M - S килобайт.
Результат округлить в практически приемлемую величину, после этого получаем число сегментов делением M на размер одного сегмента. В этом случае речь идет только о логических сегментов для получения склеивания. Они должны быть получены из физических сегментов соответствующей операцией выборки.
Например, требуется искать подстроки размером до 20 килобайт. Получаем что размер логического сегмента должен быть не больше чем32 - 20 = 12 килобайт. Округляем в ближайшую нам удобную сторону - 10 килобайт. Получаем что нужно работать со склеиванием 32 / 10 = 3 сегмента размером по 10 килобайт.
И есть очень простой вариант - если ищутся подстроки длиной не больше 16 килобайт, то подходит простое деление по 2 сегмента.
Как вариант вот две функции поиска подстроки string длиной до 16 килобайт в потоке stream:
Если данные в которых нужно найти подстроку, есть одной строкой, то это просто сделать. Есть функция $find(). А если исходные данные не могут быть представлены одной строкой, то можно применить так называемое скользящее окно и свести задачу к поиску в одной строке. Основная проблема, которую решает такой метод, состоит в поиске вхождений если искомая подстрока начинается в одном сегменте а заканчивается в другом.
Обозначим исходные сегменты:
111111
222222 333333Для поиска проводим сначала поиск в строке, полученной конкатенацией сегментов 1 и 2, потом сегментов 2 и 3 и так далее.
111111+222222 222222+333333 ....При этом мы найдем как строки 1111 и 2222 так и строку 1122.
Мы можем проводить разбиение исходных данных независимо от их физического представления на сегменты с различной длиной и объединять не по два сегмента, а больше. В имплементациях mumps существуют различные ограничения на длину строки одним куском и это естественно следует учитывать. Если ограничение как в Cache, 32 килобайта, то мы можем проводить разбиение например такими способами:
- Брать исходные данные по 16 килобайт и соединять для поиска два сегмента.
- Брать исходные данные по 10 килобайт и соединять для поиска по три сегмента.
- Брать по 8 килобайт и соединять для поиска по 4 сегмента.
- И так далее.
Результат округлить в практически приемлемую величину, после этого получаем число сегментов делением M на размер одного сегмента. В этом случае речь идет только о логических сегментов для получения склеивания. Они должны быть получены из физических сегментов соответствующей операцией выборки.
Например, требуется искать подстроки размером до 20 килобайт. Получаем что размер логического сегмента должен быть не больше чем
И есть очень простой вариант - если ищутся подстроки длиной не больше 16 килобайт, то подходит простое деление по 2 сегмента.
Как вариант вот две функции поиска подстроки string длиной до 16 килобайт в потоке stream:
FIND(stream,string) ; найти только первое вхождение n first,second,full,pos,skipped d stream.Rewind() s second="",skipped=0 s pos=0 f q:pos!stream.AtEnd d . s first=second . s second=stream.Read(16000) . s full=first_second . s pos=$f(full,string) . i pos s pos=pos+skipped-$l(first) . s skipped=skipped+$l(second) q pos
FINDALL(stream,string,out) ; выдать в @out@(i) позиции всех вхождений n first,second,full,pos,skipped d stream.Rewind() s second="",skipped=0 s pos=0 f q:stream.AtEnd d . s first=second . s second=stream.Read(16000) . s full=first_second . s pos=0 f s pos=$f(full,string,pos) q:'pos d . . s @out@($i(@out))=pos+skipped-$l(first) . s skipped=skipped+$l(second) qДля использования подстрок более чем 16 килобайт нужно внести соответствующие адаптирующие коррективы, но код приводить не буду. Желающие могут предложить свои варианты этого решения.
Комментариев нет:
Отправить комментарий