Сопоставление подстрок из словаря с другой строкой: предложения?

Question

Hellow Stack Overflow людей. Я хотел бы получить некоторые предложения по поводу следующей проблемы. Я использую Java.

У меня есть массив # 1 с количеством строк. Например, две строки могут быть: «Яблоко упало на голову Ньютона» и «Яблоки растут на деревьях».

С другой стороны, у меня есть еще один массив # 2 с такими терминами, как (Fruits => Apple, Orange, Peach; Items => Pen, Book; ...). Я бы назвал этот массив моим «словарем».

Сравнивая элементы из одного массива с другим, мне нужно увидеть, в какую "категорию" попадают элементы из # 1 из # 2. Например. Оба из № 1 подпадают под "Фрукты".

Мое самое важное соображение - это скорость. Мне нужно сделать эти операции быстро. Хорошо бы иметь структуру, обеспечивающую постоянный поиск по времени.

Я рассмотрел Hashset с методом contains (), но он не допускает подстроки. Я также попытался запустить регулярное выражение типа (apple | orange | peach | ... и т. Д.) С включенным флагом нечувствительности к регистру, но я читал, что это не будет быстрым, когда число членов увеличится (ожидается минимум 200). Наконец, я искал и рассматриваю возможность использования ArrayList с indexOf (), но я не знаю о его производительности. Мне также нужно знать, какой из терминов действительно соответствует, поэтому в данном случае это будет «Apple».

Просьба высказать свои мнения, идеи и предложения по этой проблеме.

Я видел алгоритм Aho-Corasick, но ключевые слова / термины очень часто меняются. Так что я не думаю, что смогу это использовать. О, я не эксперт в области интеллектуального анализа текста и математики, поэтому, пожалуйста, уточните сложные понятия.

Спасибо, люди, переполняющие стек, за ваше время! :)

Answer 1

Если вы используете мультикарту из Google Collections, у них есть функция для инвертирования карты (так что вы можете начать с карты типа {"Fruits" => [Apple]} и создать карту с помощью {"Apple" = > ["Fruits"]}. Таким образом, вы можете найти слово и найти список категорий для него за один вызов карты.

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

Answer 2

Будет ли дерево суффикс или аналогичная структура данных работать для вашего приложения? Он предлагает поиск строки O (m), где m - длина строки поиска, после O (n ² ) - или лучше с некоторой хитростью - первоначальная настройка, и, с некоторыми дополнительными усилиями Вы можете связать произвольные данные, например, ссылку на категорию, с полными словами в вашем словаре. Если вы не хотите кодировать его самостоятельно, я считаю, что библиотека BioJava включает реализацию.

Вы также можете добавить строки в дерево суффиксов после начальной настройки, хотя стоимость все равно будет около O (n ² ). Это, вероятно, не имеет большого значения, если вы добавляете короткие слова.

Answer 3

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

Таким образом, алгоритм будет следующим: объединить слова массива # 2, которые вы хотите найти в регулярном выражении, скомпилировать его, а затем найти совпадения в массиве # 1.

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