Как в javascript сделать игнорирование опечаток?

Question

[jarderRek]

Здравствуйте, появилась вот такая проблема:
https://codepen.io/fazras12/pen/JjMQEmq

Если вводить 'Я купил молоко' то все будет выполнятся правильно. Ну я хочу чтобы можно было опечататься, например вводить: 'Я купиил моллокко!!!####' , ' я КупИилЛ МоллОкКкОО' и так далее. Можно как то такое сделать на javascript?

Comments

[Александр]

const isSimilar = (string, needle) => {
  const expression = new RegExp(
    string
      .split(/\s+/g)
      .map(part => [...part].join('(.*?)'))
      .join('(\\s+)'),
    'i'
  );

  return expression.test(needle);
}

console.log(isSimilar('Я купил молоко', 'Я купиил моллокко!!!####' )); // true
console.log(isSimilar('Я купил молоко', 'я КупИилЛ МоллОкКкОО' )); // true
console.log(isSimilar('Я купил молоко', 'Ты купил молоко' )); // false

[Сергей Соколов]

а ещё грамматически верный вариант «Я купил молокА»

[Сергей delphinpro]

Александр, не сработает для орфографических ошибок: молоко -> малако

[Александр]

Сергей delphinpro, я полагаю, найти и заменить в part схожие буквы по типу А↔О, И↔Й, Е↔Ё↔Э и т.д. не составит проблем.

[Сергей delphinpro]

А как насчет такого:

Здравствуйте, я ваша тётя
Здрасьте, я ваша тётя

Вообще, задача не тривиальная.

[Михаил]

Александр, тут еще один момент: именно опечатка. Это когда вместо нажатия одной клавиши на клавиатуре нажимается соседняя: "Я купил мтлоко", туда же пропуски букв: "Я кпил молко"

[Сергей Сергей]

Исчо - ещё

[Александр]

Михаил, с таким превосходно справляется расстояние Левенштейна.

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

Здравствуйте, я ваша тётя	['здравств', 'я', 'ваш', 'тет']
Здрасьте, я ваша тётя		['здрасьт', 'я', 'ваш', 'тет']

тогда можно получить изменения между каждым элементом: [3, 0, 0, 0].

Пример на Python

from nltk import word_tokenize
from nltk.metrics.distance import edit_distance
from nltk.stem import SnowballStemmer

sentences = ['Здравствуйте, я ваша тётя', 'Здрасьте, я ваша тётя']

stemmer = SnowballStemmer('russian')
prepared = []
for sentence in sentences:
    tokens = word_tokenize(sentence)
    tokens = [token for token in tokens if token.isalpha()]
    tokens = [stemmer.stem(token.lower()) for token in tokens]
    prepared.append(tokens)
    
combined = zip(*prepared)
distances = [edit_distance(a, b) for a, b in combined]

print(prepared) # [['здравств', 'я', 'ваш', 'тет'], ['здрасьт', 'я', 'ваш', 'тет']]
print(distances) # [3, 0, 0, 0]

[ThunderCat]

Александр, Еще можно через гугл прогонять и использовать его готовый алгоритм перевода со школолольного на русский...

[jarderRek]

ThunderCat, Интересно, как устроен алгоритм гугла? Используется Метод Левенштейна?

Answer 1

[Михаил]

Делайте сравнение не на равенство строк, а на "примерное" соответствие с учетом возможных опечаток. Это только вы можете решить - что считать опечаткой, а что нет. Javascript не настолько умный.

Можете попробовать использовать расстояние Левенштейна (или Дамерау-Левенштейна)

Comments

[Александр]

Расстояние Левенштейна неплохое решение, но в приведенных примерах будет по 10-12 изменений, подсчитанных алгоритмом. В таком случае возникает вопрос, а какое количество изменений считать опечаткой?

[Сергей Соколов]

кажется, ТС-у подойдёт вариант с озвучиванием введённого текста и последующим распознаванием звука обратно в текст )

[Михаил]

Александр, можно попробовать модифицировать алгоритм Левенштейна, добавив туда еще одну операцию - удвоение символа. Но тут уже надо смотреть по конкретным требованиям.

[V Sh.]

Еще можно пробовать парсить строки в слова, затем искать слова или их ближайшие аналоги в словаре и склеивать обратно.

Answer 2

[rPman]

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

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

Так же, после определенной накопленной суммы разницы между строками, дальше тратить время не актуально, советую в своей реализации добавить этот параметр (особенно это актуально когда надо огромные объемы данных обработать)