Delphi: эффективный и быстрый текстовый поиск в Юникоде

Question

Есть ли быстрый и эффективный текстовый поиск в тексте / строке Unicode?Мне нужно искать часть слова тоже, а не только целое слово.

SearchBuf?

Спасибо!

Answer 1

Как уже указывалось, самый быстрый способ сделать это зависит от ряда вещей, наиболее важно, нужно ли вам иметь возможность повторного поиска или нет.Второй вопрос: насколько важно для вас действительно «самый быстрый» подход, а не достаточно быстрый, и сколько времени вы готовы потратить на оптимизацию.

Повторные поиски

Если вам требуется многократный поиск, самый эффективный способ поиска строк, о котором я знаю, - это использование суффиксных массивов (часто в сочетании с преобразованиями Берроуза-Уилера ).Этот подход широко используется в биоинформатике, где часто приходится сталкиваться с огромным количеством строковых поисков по действительно большим массивам данных (например, здесь ).Очень хорошая библиотека суффиксных массивов (и BWT) - это библиотека libdivsufsort C, но, к сожалению, я не знаю ни одного Delphi-порта этой библиотеки.(Я считаю, что эта библиотека способна обрабатывать Unicode-строки.)

Одиночный поиск

Если вам не нужно многократно искать, алгоритм поиска строк методом перебораможет быть эффективным, например, FastCode версии Pos и друзей, оптимизированных для сборки.Они, однако, были написаны до того, как Delphi был переведен в Unicode, и я не знаю подобных оптимизированных реализаций Unicode.Если бы я писал сегодня один и хотел бы оптимизировать его для современного процессора (способного к набору команд SSE4 .2), я бы серьезно посмотрел на инструкцию по сборке PCMPESTRI (ссылка pdf здесь ; см. также, например, здесь , но я понятия не имею, работает ли этот код), который может обрабатывать 2-байтовые символы, которые понадобятся вам для поиска строки в юникоде.

Answer 2

Начиная с реализации, SearchBuf медленнее, чем Pos/PosEx. Но у него есть другие варианты, такие как поиск по всему слову и регистрозависимый поиск.

Для вашей цели UnicodeString версия Pos ИМХО медленнее, чем PosEx (Pos используйте самый медленный rep scansw asm вместо двух развернутых широкоформатных сравнений для PosEx - в минимум в Delphi 2010). Так как, я думаю, вы хотели бы иметь начальное смещение для поиска (создание подстроки для вызова Pos очень медленно), вы хотели бы использовать PosEx.

A Алгоритм Бауэра-Мора может быть быстрее. Вы должны попробовать в своем приложении, на реальных данных, угадать, стоит ли это того.

И если вы хотите искать текст на английском языке, стоит попробовать UTF-8 для вашего хранилища. Поиск будет быстрее, так как вы будете использовать меньше памяти.

Но я предполагаю, что основное узкое место вашего приложения будет в части хранения / извлечения (то есть, доступ к диску или распаковка / сжатие), а не в части поиска. Используйте профилировщик программного обеспечения, чтобы угадать, что стоит улучшить:

• Сделай это прямо перед тем, как быстро. Дайте понять, прежде чем сделать это быстрее. Держите это правильно, когда вы делаете это быстрее. - Керниган и Plauger, элементы стиля программирования .
• Преждевременная оптимизация - корень всего зла. - Дональд Кнут, цитируя С. А. Р. Хоара
• Ключ к производительности - элегантность, а не батальоны особых случаев. Следует противостоять ужасному искушению подправить. - Джон Бентли и Даг Макилрой
• Правила сводятся к следующему: «1. Не оптимизировать рано. 2. Не оптимизировать пока не узнаешь, что это нужно. 3. Даже тогда не оптимизировать, пока ты знаешь, что и где нужно. "- Херб Саттер

Answer 3

Один из видов быстрого и эффективного алгоритма поиска для некоторых случаев - это тот, который (если искомые данные не меняются, и вы просто выполняете поиск снова и снова по одному и тому же содержимому буфера) выполняет поиск один раз и создает некую поисковую таблицу.,Одним из возможных решений является BoyerMoore (см. Ссылку в комментарии Руди), но, поскольку это не очень хорошо работает для символов Юникода с действительно высоким диапазоном (скажем, диапазон $ 0000 ... $ FFFF), оно все равно было быстрее, чем повторные вызовы Pos или SearchBuf,но он потреблял много памяти, когда я тестировал его с действительно расширенными наборами данных Unicode (например, китайский текст).Мое мнение, что нет никакого решения "slam dunk".

Возможно, вы могли бы написать более быстрое решение, чем Pos-но-не-так-много-как-память-как-BoyerMoore, например:

1. Создать таблицу длявсе точки персонажа и сохраните первое место, где появляется каждый символ.Я бы использовал разреженный отсортированный массив, для каждого выполненного вами поиска сохраняйте каждое начальное местоположение для этого начального символа.Это избавит вас от поиска методом грубой силы по большой строке в юникоде, которая ищет начальные совпадения символов.

2. Если в таблице нет записи для конкретного символа, вам нужно выполнить грубую силупоиск (только один раз), чтобы создать эти данные настройки.Если вы выполняете поиск один раз методом грубой силы, а кодовая точка U + 1234 не появляется, тогда запись для U + 1234 должна быть пустым массивом [], указывающим, что вам не нужно искать снова, и может быстро потерпеть неудачу при поискеначальный символ не совпадает.

3. После того, как вы нашли непустой список поиска начальных символов, например, [123,456,789], начальное совпадение кодовой точки, вы можете продолжить сделать посимвольную проверку в строке [123 ... x], затем в строке [456..x] и так далее, пока у вас не закончатся элементы в массиве.Любое несоответствие вызывает переход к следующему элементу в таблице поиска.

Опять будут патологические случаи, когда вся эта дополнительная работа приводит к тому, что код работает менее быстро, чем Pos, иесли вы не уверены, что вам нужно искать множество разных подстрок в одной и той же большой строке, то все эти «оптимизации» - пустая трата времени;Забудьте об этом, даже поиск строк Бойера-Мура выполняется медленнее, когда вы не можете повторно использовать таблицу данных поиска по крайней мере несколько раз.

Если все, что вам нужно, это функция Pos (), которая оптимизируется вручную в Assembly дляработать настолько быстро, насколько это возможно в рамках библиотечной функции, которая не создает и не потребляет хранилища промежуточных таблиц, тогда, поздравляю, Pos () уже, вероятно, работает настолько быстро, насколько вы можете (я полагаю, это было оптимизировано FastCodeлюди несколько лет назад).