Система Левенштейна возвращает неожидаемый результат

Question

Есть такие данные:

const levenshtein = require('fast-levenshtein');
let arr = [  
  'баги',
  'bots',
  'чат',
  'ботыад',
  'информация'
]

Использую такой код:

let str = 'бот'
arr.sort((a, b) => levenshtein.get(str , a) - levenshtein.get(str, b))[0]

Возвращает:

'чат'

А должно быть:

'ботыад'

Что я делаю не так?

Answer 1

Этот вопрос является продолжением вопроса Как найти самый похожий String в Array по этому и ответ на него является продолжением ответа.

В прошлом ответе я показал как применить Расстояние Левенштейна (не подошло автору) и Сходство Джаро — Винклера.

В этом ответе покажу как использовать

cтемминг, чтобы упростить поиск совпадений (стеммер - это такая штука, которая превратит ("боту", "бота", "ботом") в "бот". ну, если это слово есть в его словаре или если угадает правила по которым искать "основу" слова)
Коэффициент Сёренсена

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

const natural = require('natural');

natural.PorterStemmerRu.attach();

const userMessage = 'пешу в ппаддержку11! бот-заебот! надоели баги вашего ббота!';

const arr = userMessage.tokenizeAndStem(); // ["пеш","паддержку11","бот","заебот","надоел","баг","ваш","ббот"]

['поддержка', 'бот', 'ытот'].forEach((str) => {
    console.log('[d]', str, '->', compareDiceCoefficient(str, arr, 0.5));
    console.log('[j]', str, '->', compareJaroWinkler(str, arr, 0.7));
});


function compareDiceCoefficient(str, arr, lowerLimit = 0.05) {
    // arr.forEach((x) => console.log('[d]', x, natural.DiceCoefficient(str, x)));
    const reduced = arr.reduce((acc, x) => {
        const dt = natural.DiceCoefficient(str, x);
        if (acc.dt < dt && dt > lowerLimit) {
            acc.dt = dt;
            acc.w = x;
        }
        return acc;
    }, {dt: -Infinity, w: null});
    return reduced.w;
}

function compareJaroWinkler(str, arr, lowerLimit = 0.05) {
    // arr.forEach((x) => console.log('[j]', x, natural.JaroWinklerDistance(str, x, undefined, true)));
    const reduced = arr.reduce((acc, x) => {
        const dt = natural.JaroWinklerDistance(str, x, undefined, true);
        if (acc.dt < dt && dt > lowerLimit) {
            acc.dt = dt;
            acc.w = x;
        }
        return acc;
    }, {dt: -Infinity, w: null});
    return reduced.w;
}

[d] поддержка -> ппаддержку11
[j] поддержка -> ппаддержку11
[d] бот -> бот
[j] бот -> бот
[d] ытот -> null
[j] ытот -> null

БЛОГ НА HUSL

Система Левенштейна возвращает неожидаемый результат

Ответы (1 шт):