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

Question

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

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

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

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

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

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

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

Спасибо!

Answer 1

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

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

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

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

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

Имеет: http://illya -keeplearning.blogspot.com/2009/04/suffix-trees-java-ukkonens-algorithm.html

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

Answer 2

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

Другим лучшим решением является использование алгоритмов поиска по нескольким шаблонам, таких как: Алгоритм сопоставления строк Aho – Corasick

Answer 3

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

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

Answer 4

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

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

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

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

Answer 5

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

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