Эффективно найти список ближайших совпадений для списка слов и фраз

Question

Я ищу алгоритм, но я не знаю названия проблемы, поэтому ничего не могу найти. Надеюсь, мое объяснение проблемы имеет смысл!

Предположим, у вас длинный список фраз, где каждая фраза представляет собой набор слов. Пользователь вводит список слов, а их список «соответствует» фразе, каждое слово в фразе находится в их списке. «Счет» списка - это количество фраз, которые оно соответствует. Цель состоит в том, чтобы предоставить пользователю список слов, которые лучше всего улучшат оценку их списка.

Вот простой пример. У нас есть десять фраз:

1. древесина кабина
2. кемпинг в лесе
3. кемпингов кабина
4. весело кемпинг
5. костер
6. кемпинг огнь
7. плавания отверстие
8. весело кабина
9. древесный огонь
10. камин

И пользователь предоставляет этот список:

• древесины
• весело
• кемпинги

Мы сопрягать фразы 1 и 4, так что оценка является 2. Но если пользователь добавит «каюту» в свой список, они будут соответствовать еще 3 фразам и получить оценку 5. «огонь» добавит 2 к счет.

С тривиально коротким списком нет сложной проблемы, так как вы можете просто перебирать варианты практически без перерывов. Но, поскольку список растет до сотен тысяч, он начинает принимать сотни миллисекунд. Похоже, что должен быть способ создать индекс, чтобы ускорить процесс, но я не могу думать о структуре индекса.

Любой, кто нашел время, чтобы прочитать все это, спасибо! Надеюсь, кто-то знает, о чем я говорю.

Answer 1

Вам нужно сопоставить слова с количеством вхождений. Если вы используете хеш-таблицу, вы можете сделать это очень быстро (O (N) - с N - количеством слов во фразах) - перебирайте все фразы, разбивайте их на слова, если слово уже на карте увеличивает его count, если нет - добавьте его на карту со счетом 1.

Чтобы вычислить оценку ввода, просто переверните входные слова и скопируйте количество вхождений. O (M) - на этот раз M - количество входных слов.

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

Answer 2

Суффикс дерево.

Это довольно странные и сложные вещи, но в основном мы храним узел для каждого символа (26 * 2), затем сохраняем суффиксы для каждого символа, поэтому записи для th и an и т. Д., Но предположительно не для qj или других комбинаций, которые не будут возникать. Затем вы получаете суффиксы для них (так что, thr и т. Д., Но множество комбинаций из трех букв не разрешено). Он позволяет очень быстро искать, что не обязательно должно быть точным. Если мы хотим сопоставить a * d, мы просто следуем всем суффиксам a, а затем только d суффиксов, тогда мы настаиваем на nul.