Алгоритмы для строк “нечеткого соответствия”

Я наконец понял, что вы искали. Проблема интересная, однако, глядя на 2 алгоритма, которые вы нашли, кажется, что люди имеют совершенно разные мнения о спецификациях;)

Я думаю, было бы полезно сформулировать проблему и требования более четко.

Проблема :

Мы ищем способ ускорить набор текста, позволяя пользователям вводить только несколько букв ключевого слова, которое они на самом деле планировали, и предлагать им список для выбора.

1. Ожидается, что все буквы ввода будут в ключевом слове
2. Ожидается, что буквы во вводе будут в том же порядке в ключевом слове
3. Список возвращенных ключевых слов должен быть представлен в виде согласованный (воспроизводимый) порядок
4. Алгоритм должен быть нечувствительным к регистру

Анализ :

Первые два требования можно суммировать следующим образом: для входа axg мы ищем слова, соответствующие этому регулярному выражению [^ a] * a [^ x] * x [^ g] * g. *

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

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

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

Мое решение:

Для любого ввода я бы построил регулярное выражение, выраженное ранее. Он подходит для Python, потому что в этом языке уже есть сопоставление без учета регистра.

Затем я сопоставил бы свой (отсортированный по алфавиту) список ключевых слов и вывел бы его с таким фильтром.

В псевдокоде:

WORDS = ['Bar', 'Foo', 'FooBar', 'Other']

def GetList(input, words = WORDS):
  expr = ['[^' + i + ']*' + i for i in input]
  return [w for w in words if re.match(expr, w, re.IGNORECASE)]

Я мог бы использовать однострочник, но думал, что это закроет код;)

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

• Либо имеется несколько символов, поэтому соответствие быстрое, и длина списка не имеет большого значения
• Либо имеется много символов, и это означает, что мы фильтруем короткий список, поэтому он имеет не имеет большого значения, если сопоставление занимает немного больше времени по элементам

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