Я пытаюсь найти алгоритм, который очень быстро вычисляет минимальное расстояние Левенштейна в банке данных и выполняет как можно больше работы, прежде чем я узнаю входную строку.
У меня есть алгоритм, который читает строки с помощью алгоритма OCR. Этот алгоритм допускает много ошибок. У меня есть банк данных, состоящий из строк, которые я пытаюсь найти с помощью алгоритма OCR. Этот банк данных постоянно растет. Вполне возможно и вполне вероятно, что прочитанная строка не является частью этого банка данных, даже если она прекрасно читается алгоритмом OCR. В большинстве случаев строка с наименьшим расстоянием Левенштейна приведет к наиболее вероятному совпадению в банке данных. Итак, до сих пор я рассчитывал расстояние Левенштейна считываемой строки для каждой отдельной записи в банке данных, используя алгоритм Вагнера-Фишера. К сожалению, это единственная критичная по времени часть приложения, и она занимает некоторое время. Поэтому мне было интересно, могу ли я ускорить эту часть, предварительно заказав банк данных определенным образом, чтобы я мог быстрее вычислить наименьшее расстояние Левенштейна в банке данных. Конечно, такая предварительная структуризация сама по себе займет некоторое время, но наиболее важной частью является время между чтением строки и поиском ближайшего совпадения в банке данных.
Пока я пытаюсь найти алгоритм для предварительной структуризации данных банка данных таким образом, чтобы мне приходилось обрабатывать минимальное количество записей.
Чтобы внести ясность: я в основном спрашиваю о хороший способ быстро исключить большую часть неправильных ответов с заранее рассчитанной информацией из банка данных, а не для самого алгоритма сравнения. Это тоже было бы неплохо оптимизировать, но в основном я пытаюсь найти хороший алгоритм для эффективной фильтрации набора данных.
Подробнее здесь: https://stackoverflow.com/questions/781 ... a-databank
