Соответствие подстрокам от словаря до другой строки: предложения?
Привет люди Переполнения стека. Я хотел бы некоторые предложения относительно следующей проблемы. Я использую Java.
У меня есть массив № 1 со многими Строками. Например, две из строк могли бы быть: "Яблоко упало на главные" и "Яблоки Newton, растут на деревьях".
С другой стороны у меня есть другой массив № 2 с условиями как (Фрукты => Apple, Оранжевая, Персик; Объекты => Перо, Книга;...). Я назвал бы этот массив моим "словарем".
Путем сравнения объектов от одного массива до другого я должен видеть, в которой "категории" объекты от № 1 падают в от № 2. Например, Оба от № 1 подпали бы под "Фрукты".
Мой наиболее важный фактор является скоростью. Я должен сделать те операции быстро. Структура, позволяющая постоянное извлечение времени, была бы хороша.
Я считал Hashset с содержанием () методом, но это не позволяет подстроки. Я также пытался выполнить regex как (apple|orange|peach |... и т.д.) с нечувствительным к регистру флагом на, но я считал, что это не будет быстро, когда условия увеличатся численно (минимальные 200, которые будут ожидаться). Наконец, я искал и рассматриваю использование ArrayList с indexOf (), но я не знаю о его производительности. Я также должен знать, какое из условий на самом деле соответствовало, так в этом случае, это была бы "Apple".
Обеспечьте свои представления, идеи и предложения на этой проблеме.
Я видел алгоритм Aho-Corasick, но ключевые слова/условия, очень вероятно, будут часто изменяться. Таким образом, я не думаю, что могу использовать это. О, я не эксперт в анализе текста и математике, поэтому уточните сложные понятия.
Спасибо, люди Переполнения стека, в течение Вашего времени!:)
3 ответа
Если Вы используете мультикарту из Google Collections, то у них есть функция инвертирования карты (так что Вы можете начать с карты типа {"Фрукты" => [Apple]}, и создать карту с помощью {"Apple" => ["Фрукты"]}. Таким образом, вы можете искать слово и находить список категорий для него, за один вызов карты.
Я бы ожидал, что сам захочу разделить строки и искать слова на карте по очереди, чтобы я мог делать поиск (подгонку под разные окончания слов) и стоп-фильтрацию. Использование карты должно получить хорошее время поиска, плюс это легко попробовать.
Если вам нужно искать только 200 терминов, регеxps может на самом деле работать на вас. Конечно, регулярное выражение большое, но если вы скомпилируете его один раз и просто используете этот скомпилированный Pattern, то время поиска, вероятно, будет линейным по суммарной длине всех строк в массиве#1, и я не понимаю, как вы можете надеяться на лучшее.
Итак, алгоритм будет следующим: скомпилируйте слова array#2, которые вы хотите искать в регулярном выражении, скомпилируйте их, а затем найдите совпадения в массиве array#1 .
(Регулярные выражения компилируются в машину состояний - т.е. на каждом символе строки он просто выполняет поиск таблицы для следующего состояния. Если регулярное выражение сложное, возможно, у вас будет обратный ход, который увеличивает время, но ваше регулярное выражение имеет очень простую структуру)
.Будет ли суффиксное дерево или аналогичная структура данных работать для вашего приложения? Он предлагает поиск по O(m) строке, где m - длина строки поиска, после O(n2)--или лучше с некоторой начальной установкой триккера, и, с некоторыми дополнительными усилиями, Вы можете ассоциировать произвольные данные, такие как ссылка на категорию, с полными словами в Вашем словаре. Если вы не хотите кодировать его самостоятельно, я полагаю, что библиотека BioJava включает в себя реализацию.
Вы также можете добавлять строки в суффиксное дерево после начальной установки, хотя стоимость все равно будет около O(n2). Вероятно, это не так уж и сложно, если вы добавляете короткие слова.