Алгоритмы поиска строк в Java

Я выполняю сопоставление строк с большим объемом данных.

РЕДАКТИРОВАТЬ: я сопоставляю слова, содержащиеся в большом списке, с некоторыми текстовыми файлами онтологии. Я беру каждый файл из онтологии и ищу совпадение между третьей строкой каждой строки файла и любым словом из списка.

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

Я сделал это с помощью Radix. Попробуйте; это было очень быстро и хорошо работает, но теперь я думаю, что моя работа бесполезна, потому что trie возвращает только точные совпадения. :/

  • Алгоритмы, которые делают это, являются алгоритмами поиска строк?
  • Может ли кто-нибудь предложить некоторые реализации Java, с которыми у него есть опыт?

Алгоритм должен быть быстрым, но не является главным приоритетом, так как скорость и сложность будут скомпрометированы.

Буду очень благодарен за все советы/примеры/пояснения/ссылки!

Спасибо!


java matching algorithm string-matching string-search
person Julia    schedule 16.07.2010    source источник
comment
Что такое Тип алгоритмов, которые делают это, являются алгоритмами поиска строк? спрашиваешь?   -  person Svante    schedule 17.07.2010

Ответы (5)


arrow_upward
4
arrow_downward

Вы можете найти полезными деревья суффиксов (по своей концепции они аналогичны попыткам).

К каждой строке вы добавляете ^ и заканчиваете $ и создаете суффиксное дерево всех добавленных строк. Использование пространства будет O (n) и, вероятно, будет хуже, чем у вас было для попытки.

Если вам теперь нужно найти строку s, вы можете легко сделать это за время O(|s|), точно так же, как и в случае с trie, и совпадение, которое вы получите, будет совпадением подстроки (по сути, вы будете сопоставлять какой-то суффикс некоторой строки ).

Извините, у меня нет под рукой ссылки на реализацию Java.

Нашел полезный ответ stackoverflow: Обобщенная реализация суффиксного дерева Java

Который имеет: http://illya-keeplearning.blogspot.com/2009/04/suffix-trees-java-ukkonens-algorithm.html

Что, в свою очередь, имеет: Исходный код: http://illya.yolasite.com/resources/suffix-tree.zip

person Community    schedule 16.07.2010
comment
@Moron: Я думаю, что это может быть именно то, что мне нужно, если я хорошо понимаю, я могу сопоставить и содержать с тем же деревом???? - person Julia; 17.07.2010
comment
@Юлия: Да, точно. Если вам нужно точное совпадение, добавьте к строке поиска ^, добавьте $ и выполните поиск. Если вы хотите содержит, используйте строку поиска как есть. - person ; 17.07.2010
comment
@Moron: ‹вздох› Кажется, это было бы идеально. Должна быть какая-то java lib!! - person Julia; 17.07.2010
comment
@Julia: Посмотрите ссылки, которые я добавил к этому ответу. - person ; 17.07.2010

arrow_upward
2
arrow_downward

вы можете использовать алгоритм BM для поиска в текстовых файлах по одному шаблону, и повторите этот алгоритм для всех шаблонов, которые у вас есть в вашем списке.

другое лучшее решение — использовать алгоритмы поиска с несколькими шаблонами, такие как: алгоритм сопоставления

person Wajdy Essam    schedule 16.07.2010
comment
johannburkard.de/software/stringsearch ? Вы говорите поиск в текстовых файлах, но мне не нужно совпадение где-либо в текстовом файле, а каждую третью строку из каждой строки, что можно указать? (извините за подробности, я боюсь торопиться с чем-то, как я сделал с radix trie) - person Julia; 17.07.2010
comment
Алгоритм BM сопоставляет любую строку без учета источника строк (из текста в файле, из ячейки в БД... и т.д.). - person Wajdy Essam; 17.07.2010

arrow_upward
1
arrow_downward

Регулярные выражения, безусловно, ваш лучший выбор. Их может быть немного запутанно писать, но это единственный способ получить более слабое соответствие без непонятной серии операторов if/else или switch.

Кроме того, они будут намного быстрее, чем альтернатива.

person chimeracoder    schedule 16.07.2010
comment
-1: Почему регулярное выражение «лучшее»? Почему альтернативы операторам if/else переключаются? Какие другие альтернативы вы рассматривали, прежде чем утверждать, что альтернативы медленнее? Я бы сказал, что производительность регулярных выражений будет довольно плохой! Вы должны скомпилировать их, а затем, возможно, вернуться во время сопоставления и т.д. - person ; 17.07.2010
comment
Ну, как изначально был сформулирован вопрос (предварительно отредактировать), так я его и прочитал - очевидно, он уже не актуален! - person chimeracoder; 19.07.2010

arrow_upward
0
arrow_downward

Я не совсем уверен, правильно ли я понял вопрос, но похоже, что регулярные выражения сделают эту работу.

http://java.sun.com/developer/technicalArticles/releases/1.4regex/

person Xzhsh    schedule 16.07.2010

arrow_upward
0
arrow_downward

Почему бы вам не использовать метод indexOf в java. По наличию памяти прочитайте содержимое. Сделайте indexOf и получите все нужные вам строки. Загрузите следующий набор содержимого.

При чтении из файла используйте потоки nio.

Может идея плохая, но я верю в java. Он будет использовать лучший алгоритм.

Лучше, если вы используете регулярное выражение.

person Mukeshkoshym    schedule 11.04.2013