Построить дерево суффиксов конкатенации из миллиона слов и запросить его с помощью набора тестов, чтобы найти наиболее близкое соответствие и классифицировать

Question

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

Мое решение: Первоначально я использовал эту грубую силу, которая не масштабируется.Теперь я думаю, что строю дерево суффиксов для конкатенации обучающих корпусов (O (n)) и запрашиваю тестирующие корпуса (постоянное время).Попытка сделать это в Python.

Я ищу инструменты или пакеты, которые помогут мне начать работу, или другие более эффективные способы решения проблемы.Заранее спасибо.

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

Answer 1

Какую метрику расстояния вы используете для наиболее близкого соответствия?

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

Примером этого является Поиск сходства строк Top-k с ограничениями редактирования-расстояния (2013) https://doi.org/10.1109/ICDE.2013.6544886 https://scholar.google.com/scholar?cluster=13387662751776693983
Представленное решение позволяет избежать вычисления всех записей в таблице при добавлении столбцов.

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