Приблизительное сопоставление строк с буквой путаницы Matrix?

Question

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

Тем не менее, я хочу, чтобы соответствие было фонетически мотивировано, например, «M» и «N» фонетически похожи, поэтому стоимость замещения «M» для «n» должна быть небольшой, по сравнению с «м» и «K ". Итак, если я ищу [Mein] «Главный», это будет соответствовать последовательности письма [MEIM] «MAIM», скажем, стоить 0,1, тогда как это будет соответствовать последовательности письма [Meik] «сделать» с, скажем стоимость 0,7. Точно так же существуют разные затраты для вставки или удаления каждой буквы. Я могу поставить путаницу матрицы, которая для каждой буквенной пары (X, Y) дает затраты на замену x с помощью y, где x и y - любая буква или пустая строка.

Я знаю, что есть доступные инструменты, которые делают приближенное совпадение, такое как agrep, но насколько я могу сказать, они не принимают путаницу матрицы в качестве ввода. То есть стоимость Любые Вставка / замена / удаление = 1. Мой вопрос в том, есть ли какие-либо инструменты с открытым исходным кодом уже доступны, которые могут сделать приближенное совпадение с путаницей матрицами, а если нет, какой хороший алгоритм, который я могу реализовать для этого?

Редактировать: Просто чтобы быть понятным, я пытаюсь изолировать приближенные случаи слова, такого как [Mein] из более длинной строки, например [AiammeinLimeiking ...]. В идеале, алгоритм / инструмент должен сообщать о таких случаях, как [Mein] с стоимостью 0,0 (точное совпадение), [Meik] с стоимостью 0,7 (ближнего спичка) и т. Д. Для всех приблизительных строковых совпадений со стоимостью ниже данного порога.

Answer 1

Я не знаю о любых фонетических признаках, которые используют путаницу матрицы. я знаю Soundex., а также рейтинг матча.

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

Answer 2

Питер Клейвег Коврик / l04. (для вычислительной диалектологии) включает в себя реализацию расстояния Левенштейна, который позволяет указывать неравномерную вставку, удаление и затраты на замену.