Как работает неточное сравнение строк

В поисковых системах какой алгоритм применяется в поисковой строке?

Вам нужен стемминг. Можете попробовать стеммер Портера.

Простой коэффициент Жаккара не подойдёт?

Cosine similarity ещё, https://en.wikipedia.org/wiki/Cosine_similarity, но оно в общем случае считает все перестановки одинаковыми (похожесть кот на ток равна 1). Иногда это очень нужная фича.

Я что-то похожее писал на коленке лет 28 назад, для быстрого поиска имён в адресной книге (поиск по мере набора имени). Там я добавил идею о близком равенстве отдельных множеств букв. Например, буквы е и ё можно считать равными, а буквы с и з, и и е, д и т - близкими. Ну и так далее. Также, учитивались возможные удвоения. Хоть алгоритм был придуман и написан на коленке, но для имён/фамилий он работал очень неплохо.

Держите лучше расстояние Карловского:

function karlovskiy_distance( left: string, right: string ) {

	left = '\b\b' + left + '\f\f'
	right = '\b\b' + right + '\f\f'

	let dist = -4

	for( let i = 0; i < left.length - 2; ++ i ) {
		if( !right.includes( left.slice( i, i+3 ) ) ) ++ dist
	}

	for( let i = 0; i < right.length - 2; ++ i ) {
		if( !left.includes( right.slice( i, i+3 ) ) ) ++ dist
	}

	return Math.max( 0, dist ) / ( left.length + right.length - 8 )
  
}

я пришёл к себе домой | я пришел домой к себе = 0.29
июнь | июль = 0.25
кот | для = 1
кот | кот = 0

Ответ всегда должен получаться от 0 до 1, где 0 - точное совпадение слов, 1 - полное не совпадение слов.

Что-то не сходится. 0 может быть только если не совпала ни одна буква.

То есть для примера сравним варан и комод.

Расстояние по вашей формуле равно нулю, но слова совсем не похожи.

Нечёткое сравнение строк https://habr.com/ru/post/341148/

Какая здесь теплая лаповая атмосфера! Друзья, а может быть у кого-нибудь появится хорошая идея или он что-то видел похожее насчет задачи, которую лично мне было бы интересно решить. Задача в следующем.

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

Н-граммы разной длины во всех своих проявлениях и хаки с сортировкой слов по буквам (вот оригинальный блог пост).

В сочетании с существующими библиотеками по оптимизированному расчету расстояний Левенштейна или KNN (k-nearest neighbour search) можно сделать поиск и индекс любой сложности и нужности.

Мне кажется у Джаро есть недостаток. Этот алгоритм не отражает то, что человек "подразумевает" под похожестью.
В статье сравниваются слова:

создание

обедать

И итоговое расстояние получается:

d = (1 / 3) * ( 3 / 8 + 3 / 7 + (3 - 0.5) / 3 ) ≈ 0.33 * ( 0.36 + 0.43 + 0.83 ) ≈ 0.53

Предположим мы уберем лишнюю, не совпадающую букву "с".

оздание

обедать

Тогда слова должны стать "более похожими", но изменится выравнивание букв "да". И это значительно изменит результат алгоритма.

d = (1 / 3) * ( 3 / 7 + 3 / 7 + (3 - 1) / 3 ) ≈ 0.33 * ( 0.42 + 0.42 + 0.33 ) ≈ 0.39
Получается, убрав лишнюю букву, которая мешала совпадению, мы только уменьшили "похожесть". А вот расстояние Левенштейна тут покажет правильную тенденцию.