Как работает неточное сравнение строк / forpes.ru

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

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

13.06.2022 17:09

vgaidadei 38 10000 Источник

Недавно я писал API для динамически меняющихся обоев. Обои меняются каждый день, но могут и каждые 2 часа в зависимости от обстановки в мире, например, если вышла какая-то экстраординарная новость, то показывает картинку в соответствии с данной новостью или сейчас проходит какой-то праздник, соответственно также показывает картинку с данным праздником. Если вам интересно и вы хотите помочь проекту (нужно разработать очень простые приложения для android, ios, windows, mac и т.д. все права на приложения принадлежат вам я их опубликую на сайте проекта), вот ссылка на данный проект (можете также писать в личку на этом сайте):

landing page = https://fakt309.github.io/thisisthewall

github repository = https://github.com/fakt309/thisisthewall

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

Начало

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

"test" == "test" //true
"test" == "test1" //false

Но вот что если мы хотим не просто получать дискретное значение (true / false), а дифференцированное, например в процентах. Ведь согласитесь строки test и testing гораздо ближе к друг другу, чем test и abcd. Для данной проблемы существует множество решений, мы поговорим о самых популярных алгоритмах (также об их модификациях):

Расстояние Хэмминга
Расстояние Левенштейна
Сходство Джаро — Винклера
Коэффициент Сёренсена

Также сравнивать строки можно с мощью нейросетей, но в данной статье речь будет идти именно об четырёх выше перечисленных способах.

Расстояние Хэмминга

Имея множество слов, мы можем задать правило по которому будем вычислять расстояние между словами, аналогично тому как мы вычисляем в пространстве точек расстояние между точками, также мы можем задать правило по которому будем вычислять расстояние между словами. Чем больше это расстояние, тем меньше похожи слова и наоборот. Самый простой пример это расстояние Хэмминга. Данное правило работает только для слов одинаковой длины и вычисляется как число позиций отличающихся символов, пример, сравним два слова:

ромашка

монашка

В данном случае 2 позиции отличаются (первая и третья), значит расстояние 2, другой пример:

карта

каток

Здесь расстояние 3, так как 3 позиции отличаются (третья, четвёртая и пятая).

Как не трудно понять максимально расстояние между словами равно длине сравниваемых слова.

Для любой длины и любого q-ичного алфавита мы можем получить все возможные вариации данного слова и составить метрическое пространство. Возьмем тривиальный пример с алфавитом [0, 1] и длиной слова 3. Получаем всего 8 слов: 000, 001, 010, 011, 100, 101, 110, 111. Из данных слов мы можем построить трёхмерный куб, на вершине которого будут расположены наши слова, смотри на картинке:

Здесь мы видим слова, которые находятся на диагонали куба имеют максимальное расстояние, например 100 и 011 (отличаются в каждой позиции) расстояние равно 3. Слова которые находятся на диагонали квадратов, имеют меньшее расстояние, например слова 000 и 101 (отличаются в двух позициях) имеют расстояние 2. И самое маленькое расстояние тех слов что находятся на одинаковых рёбрах, например 010 и 110 имеют расстояние 1 (отличаются в одной позиции). В данной метрике выполняются все необходимые аксиомы (тожества, симметрии, неравенство треугольника) так что это полноценное метрическое пространство.

Недостатки расстояния Хэмминга:

Работает только для одинаковой длины слов (очень существенный недостаток)

Преимущества расстояния Хэмминга:

Легко реализуемый алгоритм и понятный
Наиболее точно измеряет расстояние между строками

Расстояние Левенштейна

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

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

Имея данные односимвольные операции мы можем преобразовать одно слово в другое. Расстояние по Левенштейну между двумя словами определяется как минимальное количество односимвольных операций, необходимых для преобразования из одного слова в другое. Пример:

удачливый

удачный

В данном примере было удалено 2 символа (л и и) и один символ заменён (в на н), всего три операции, значит расстояние равно 3.

Также каждой операции можно задавать свою цену, в прошлом примере цена каждой операции равнялась 1 и поэтому длина равна трём, если мы примем что замена равняется 0.5, вставка 0.7, а удаление 0.3, то получим уже расстояние в примере выше равное 1.1. Также цена операции может зависеть от символа, к которому применяется, например если мы удаляем символ а, то это одна цена, если удаляем символ б, уже другая цена, установка цен каждой операции делается вручную, если она необходима.

Недостатки расстояния Левенштейна:

Трудно находить минимальное число односимволных операций (но есть Алгоритм Вагнера-Фишера)
При перестановке слов показывает большие расстояния (например в словах хороший день - день хороший)
Расстояния между короткими, но совершенно разными словами - небольшие, в то время как между длинными строками, но похожими - большие (например кот - для маленькое расстояние, в то время как: я пришёл к себе домой - я пришел домой к себе большое расстояние)

Преимущества расстояния Левенштейна:

Работает для разных длин строк
Относительно не сложный в понимании способ (но сложный в вычислении)

Расстояние Дамерау - Левенштейна

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

Расстояние Джаро

Данный метод гораздо проще будет объяснить на конкретном примере. Давайте рассмотрим два слова: создание - обедать

Для начала мы посчитаем количество точных совпадений (то есть совпадает значение и порядковый номер буквы) и запишем в переменную e

создание

обедать

У нас получилось e = 2

Далее мы вычисляем длину совпадений, назовем ее l (позже вы увидите для чего она нужна) по формуле: floor( max( str1.length, str2.length ) / 2 ) - 1

У нас получается : floor ( max ( 8, 7 ) / 2 ) - 1 = floor( 8 / 2 ) - 1 = floor ( 4 ) - 1 = 4 - 1 = 3 , итого l = 3

Теперь мы находим количество неточных совпадений, назовём ее z данное количество вычисляется следующим образом берём: каждую n-ую букву первого слова и сверяем с каждой буквой n ± l , но не с точным совпадением, пример показан ниже на картинке:

Как видно из картинки например буква а пятая по счёту, значит сравниваю данную букву со всеми буквами второго слова 5 ± 3, кроме пятой буквы (то есть 2, 3, 4, 6, 7, 8) и так проделываем со всеми буквами первого слова, получаем количество неточных совпадений. В моем случае получилось z = 1

Теперь обозначим новые переменные как m = e + zи t = z / 2

И в итоге формула расстояния Джаро будет выглядеть так:

Здесь |s₁| , |s₂| - длины первой и второй строки

В моем случае:

m = 2 + 1 = 3

t = 1 / 2 = 0.5

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

Наше расстояние получилось 0.53

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

Преимущества расстояния Джаро:

Работает с разной длиной строк
Довольно точно считает на практике
Выдает нормированный результат (то есть от 0 до 1)

Сходство Джаро - Винклера

Самый эффективный метод (на мой взгляд), который я лично использовал в своём проекте. Работает по такому принципу: сначала мы находим расстояние Джаро, затем задаем коэффициент масштабирования p (по стандарту рекомендуется 0.1, можно менять но оно не должно превышать 0.25) и находим расстояние Джаро - Винклера следующим образом:

Сначала считаем длину совпадающего префикса и записываем в переменную l (это количество первых совпадающих символов) например в словах комитет - комиссия количество первых букв совпадающих равняется 3, а в словах нить - натрий l = 1

Пусть d -расстояние Джаро между словами s₁ и s₂ , p - коэффициент масштабирования, l - длина совпадающего префикса, тогда формула Джаро - Винклера выглядит следующим образом:

j = d + (l * p ( 1 - d ))

Преимущества расстояния Джаро - Винклера:

Даёт бонусную надбавку словам с одинаковыми префиксами, что зачастую повышает точность вычисления схожести по сравнению с расстоянием Джаро

Недостатки расстояния Джаро - Винклера:

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

Коэффициент Сёренсена

Коэффициент Сёрнсена придуман для определения схожести любых множеств. В случае со словами его также удаётся применить.

Представим у нас есть два множества A = [a , b, c] и B = [b, c, d, e] вычислим коэфициент Сёренсена для данных множеств по формуле:

K = 2 * |A∩B| / (|A| + |B|)

где A∩B - пересечение множеств, |A| - мощность множества (количество элементов в конечном множестве)

В нашем случае

A∩B = [b, c]

|A∩B| = 2

|A| = 3

|B| = 4

Получаем K = 2 * 2 / (3 + 4) = 4 / 7 = 0.57

Теперь как мы это применим к словам. Слова мы можем представить как множества, например возьмем два слова: звено - зерно

Первое слово можем представить как множество [з, в, е, н, о]

Второе слово можем представить как множество [з, е, р, н, о]

Но здесь есть проблема: в множествах отсутствует порядок, и таким образом если мы будем считать коэффициент Сёренсена для данных множеств, то при перестановке букв местами коэффициент не будет меняться совсем, поэтому есть решение, представлять слово в виде множества биграмм, то есть последовательности из двух букв, смотрите на примере.

Слово звено превращаем в множество биграмм: [зв, ве, ен, но]

Слово зерно превращаем в множество биграмм: [зе, ер, рн, но]

Здесь как мы видим каждый элемент множества состоит из последовательности двух букв идущих по порядку в слове. Теперь просто для данных множеств считаем коэффициент Сёренсена как мы делали выше

K = 2 * 1 / (4 + 4) = 2 / 8 = 0.25

Данный метод довольно экзотический и я редко сталкивался с ним на практике как метод расчёта схожести строк.

Итог

На мой взгляд самый лучший метод расчёта Сходство Джаро - Винклера или же просто расстояние Джаро, выдает самые лучшие результаты относительно не сложные алгоритмы вычисления плюс нормированный результат, который можно переводить в проценты. Также имеет смысл рассматривать расстояние Левенштейна (или Дамерау - Левенштейна), но только если грамотно вручную установить каждой операции цену, тогда это может работать, но я так и не смог это осилить. Растояние Хэмминга работает неплохо и максимально простое, но большой минус что работает только для одинаковых длин строк, может подойти в генетике, где сравниваются гены равной длины.

Если кому интересен проект, присоединяйтесь мне нужно написать приложения которые берут картинку по ссылке из api и устанавливают на рабочий стол каждые 2 часа, по сути приложение очень простое, если кто умеет, буду благодарен (android, ios, windows, macOS, расширение для chrome кто что умеет делать, ваши работы выложу на своем сайте).

landing page = https://fakt309.github.io/thisisthewall

github repository = https://github.com/fakt309/thisisthewall

Комментарии (38)

Didimus
13.06.2022 18:39
#24434662
+2
В поисковых системах какой алгоритм применяется в поисковой строке?
1. TsarS
  13.06.2022 19:54
  #24434824
  +1
  https://yandex.ru/dev/mystem/
1. jia3ep
  14.06.2022 15:24
  #24436996
  Для автоподсказок в поисковой строке на первый взгляд можно было бы использовать какое-нибудь модифицированное префиксное дерево (trie).

iboltaev
13.06.2022 19:16
#24434744
+1
Вам нужен стемминг. Можете попробовать стеммер Портера.

itHauntsMe
13.06.2022 20:02
#24434842
+1
Простой коэффициент Жаккара не подойдёт?

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

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

nin-jin

14.06.2022 01:01

#24435240

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

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

Deosis
14.06.2022 07:06
#24435346
+1
Ответ всегда должен получаться от 0 до 1, где 0 - точное совпадение слов, 1 - полное не совпадение слов.

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

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

Расстояние по вашей формуле равно нулю, но слова совсем не похожи.
1. DfyzET
  14.06.2022 20:35
  #24437902
  Верно подметили.
  На самом деле ровно наоборот: 1 - точное совпадение, 0 - полное не совпадение.
  
  Это написано тут, например. Или даже банально на англ вики
  Я подозреваю путаница возникла так как автор поста подсмотрел на рус вики, где сейчас стоит как раз непровереная версия статьи с неверная информация по поводу ответов.

Denxc
14.06.2022 08:30
#24435424
+1
Нечёткое сравнение строк https://habr.com/ru/post/341148/

Sergey_Kovalenko
14.06.2022 10:36
#24435784
+2
Какая здесь теплая лаповая атмосфера! Друзья, а может быть у кого-нибудь появится хорошая идея или он что-то видел похожее насчет задачи, которую лично мне было бы интересно решить. Задача в следующем.

У вас есть достаточно длинный текст на естественном языке, похожем на английский или русский, однако в нем удалены все пробелы между словами, все знаки препинания и все большие буквы заменены маленькими. Можно ли не пользуясь словарями и любыми другими источниками данных придумать алгоритм, который достаточно точно поделит этот текст на слова?
1. nin-jin
  14.06.2022 10:51
  #24435848
  +1
  Разве что нарезать по словарю невозможных биграм. А кто и зачем эти пробелы вырезал?
  1. Sergey_Kovalenko
    14.06.2022 12:04
    #24436198
    +1
    Так, словаря по условию нет, грамматика не известна, тренировка на сторонних данных запрещена.
    
    Задача - праздный вопрос. В устной речи нет пробелов и заглавных букв. Также мне известны искусственные языки, смысл предложений в которых задается их грамматикой. Не точно, конечно, но с точностью до изоморфизма. Сообщения на таких языках вы сможете послать любой разумной расе во вселенной безо всякого переводчика или предположений о подобии их культуры нашей и они вас поймут.
    
    В связи с этим появился праздный вопрос, на сколько грамматическая и смысловая структура естественных языков может быть выявлена из статистических закономерностей речи.
    
    vedenin1980
    14.06.2022 15:33
    #24437022
    Можно выделять повторящиеся комбинации букв, получая возможные слова, чуть сложнее выделение приставок, корней, суфиксов и окончаний для получения возможных правил склонений. Но это если предполагать, что грамматика языка похожа на грамматику европейских языков, а не построена на иероглифах или еще более сложной системе, где нет постоянных слов, например.
    
    Сообщения на таких языках вы сможете послать любой разумной расе во вселенной безо всякого переводчика или предположений о подобии их культуры нашей и они вас поймут.
    
    Это не реально, чтобы сообщение мало-мальски было понятно нужно посылать видео файлы или наборы фотографий. Любой текст и любая грамматика требует общей культуры и логики, либо долгого обучения.
    
    Sergey_Kovalenko
    14.06.2022 18:12
    #24437532
    -1
    Я тоже думал, что невозможно. Так много, где утверждается - но все эти утверждения ошибочны.
    Хорошо исписанная тетрадь по арифметике 3-го класса не самым неряшливым и отсталым учеником содержит достаточно закономерностей, чтобы быть понятной любой достаточно развитой цивилизации, даже если та никак не знакома с культурой Земли.
    
    vedenin1980
    14.06.2022 19:23
    #24437732
    +1
    У вас тут слишком много недоказанных утверждений. Даже математика инопланетной цивилизации может отличаться очень кардинально (даже 2+2 в их математике будет не равно 4 (точнее не всегда равно), например потому что 2 литра спирта и 2 литра воды не дадут 4 литра смеси), а уж система записи вообще быть совершенно другой.
    Банально, у них давно все на биологических компьютерах с системой счисления по основанию пи без целых и отрицальных чисел в принципе, а тетрадка с закорючками вообще не воспринимается как носитель информации.
    
    Sergey_Kovalenko
    14.06.2022 19:27
    #24437744
    -2
    достаточно развитая - значит способная воспринимать закономерности окружающего мира и формировать новые понятия. Символьные последовательности в тетрадке по арифметике проявляют закономерности. Основываясь на них, разумная цивилизация сможет сформировать новое понятие десятичной арифметики и натурального числа, даже если до этого они ей не были известны. Чем они думают и какая у них математика - не важно.
    
    vedenin1980
    14.06.2022 22:04
    #24438050
    +1
    Символьные последовательности в тетрадке по арифметике проявляют закономерности. Основываясь на них, разумная цивилизация сможет сформировать новое понятие десятичной арифметики и натурального числа, даже если до этого они ей не были известны
    
    Ну вы считаете себе представителем разумной цивилизации? Ну вот вам математическая запись
    
    Сможете рассказать, какие математические формулы там записаны не используя гугл или хотя бы как вы сможете понять закономерности? Учитывайте, что это все-таки Земная цивилизация наш предок, от которой мы унаследовали многие принципы современной цивилизации. Сложность расшифровки записей инопланетной цивилизации может быть на пару порядков выше.
    
    Обратите внимание, вы не знаете тут ни систему счисления, ни в какую сторону записываются формулы, ни какие символы будут символами операций, ни как записывается числа (десятичная позиционная система далеко не единственная возможная), более того у вас совершенно нет понятия, какие математические действия тут вообще записаны, может 2+2, а может двойные интегралы, с производными, синусами и косинусами.
    
    Даже если у вас совпадает математическая логика, ни зная ничего о записавшей цивилизации, расшифровка тут очень нетривиальна. Если же понятия совсем разные — практически невозможна.
    
    Ваша земная тетрадка по математики для инопланетян, которые вообще ничего про Землю не знают, тоже скорее всего будет просто набором символов. По-крайне мере утверждать, что Любая цивилизация легко ее расшифрует очень уж антропоцентричное утверждение (предположение, что инопланетная цивилизация условных плазменных сгустков имеет схожую логику, принципы математики, системы записи формул и т.п.)
    
    nin-jin
    14.06.2022 22:22
    #24438096
    Я даже больше скажу, даже современные математики всё никак не придут к консенсусу которая из уже существующих математических логик более корректна.
    
    Sergey_Kovalenko
    14.06.2022 22:23
    #24438102
    Простите, что разрушил ваши представления о мире, я сам был обескуражен, когда впервые осознал эти идеи.
    
    Теперь, что касается вашего манускрипта. Если там действительно проявляются закономерности, то можно попытаться их найти. Текста мало, откровенно мало, на исписанную тетрадь не тянет, хотя отдельные "буквы" в общем-то просматриваются. Сам я конечно же не стану тратить вечер или неделю, чтобы решить этот ребус, когда он уже кем-то решен. Но, если бы он не был решен, или тем более был посланием из космоса, то пара сотен умнейших людей лбы над ним бы поморщило.
    
    gchebanov
    14.06.2022 15:44
    #24437060
    +1
    Минимизируешь энтропию текста деленного на слова + энтропию словаря, по всем разбиениям. Если делить посимвольно (все слова из одной буквы), словарь получаеться маленький, а текст большой. С другой стороны если взять весь текст как одно слово - тогда на сам текст будет приходиться 0 энтропии, а словарь будет стоить как весь текст без сжатия (с перплексией алфавит на символ). При этом частые сочетания (фразеологизмы) и популярные предлоги скорее всего слипнуться в одно слово. Еще можно добавить штраф за длину слов / KLD между словарем и ципфром.
    
    Sergey_Kovalenko
    14.06.2022 18:06
    #24437512
    Как считать энтропию словаря? Энтропия одноэлементного множества не равна нулю?
    
    gchebanov
    14.06.2022 19:10
    #24437696
    +1
    log(alphabet) * сумму длин всех слов.
    
    Я попробовал что получается на тексте полученном из статьи, написал жадный алгоритм, сейчас посмотрим что выйдет.
    
    Начинаю с односимвольных слов, сливаю соседние жадно.
    
    https://pastebin.com/q8Jnkfkh
    
    gchebanov
    14.06.2022 19:16
    #24437714
    +1
    Вот концовка
    
    https://pastebin.com/fZ5eGa0U
    
    Видно что жадность плохо работает, нужно еще и пересобирать слова.
    
    Пример: "есл им ы" встречается 4 раза, и хотя мы добавили в словарь пару (есл, и), мы не можем ничего сделать с уже построенным "им".
    
    Sergey_Kovalenko
    14.06.2022 19:29
    #24437750
    +1
    Красиво. Даже на маленькой статье вырисовываются знакомые очертания некоторых слов. А томик войны и мира ваша программа переварить сможет?
    
    gchebanov
    14.06.2022 20:16
    #24437854
    +1
    Асимптотика не та, но я попробовал.
    
    315058.332 204.849 гово ри 49 41162 394 314857.649 200.682 ихай лов 28 41134 394 314657.976 199.673 нул ся 30 41104 395 314547.888 110.087 лов на 73 41053 396 314315.691 232.197 че лов 49 41004 397 314123.157 192.534 напа в 51 40953 398 313921.508 201.648 пер е 71 40882 399 313741.424 180.084 ма лень 27 40855 400 313551.339 190.086 гово рила 29 40826 401 313376.408 174.931 кото рый 26 40800 402
    
    298986.794 256.386 сказа л 78 36302 622 298732.565 254.230 челов е 49 36253 622 298492.642 239.922 княги ня 42 36211 623 298281.436 211.206 те перь 30 36181 623 298093.330 188.106 петер бур 17 36164 623 297918.569 174.761 васи лий 23 36141 624 297746.231 172.338 про дол 29 36112 625 297587.984 158.247 прос и 42 36070 626 297442.206 145.777 какбуд то 29 36041 627 297289.781 152.426 графи ня 27 36014 628 297156.175 133.605 приба ви 19 35995 628 297040.460 115.715 все гда 17 35978 628 296925.564 114.897 улыба ясь 19 35959 629 296811.075 114.488 стве нно 22 35937 630 296681.633 129.442 сказа лаона 28 35909 631 296573.243 108.390 с мотре 24 35885 631 296472.848 100.395 м ихайлов 26 35859 632
    
    Что-то получилось https://pastebin.com/6xk0ZipK
    
    Sergey_Kovalenko
    14.06.2022 20:28
    #24437882
    Ну, зато идея простая и интересная. На асимптотику вы кстати еще не вышли. Я подозреваю, если ваш алгоритм масштабировать на ленинскую библиотеку, то размер словаря перестанет быть сильным ограничением и в него начнут попадать частые словосочетания или даже целые крылатые фразы. Но мне все равно понравилась ваша мысль насчет энтропии. Быть может через годик другой она дозреет до результата достойного научной статьи.
    
    gchebanov
    14.06.2022 20:39
    #24437912
    +1
    Я имел в виду time complexity, у меня что-то между O(n^2) и O(n^3).
    
    Вот тут код, я наигрался с ним, как минимум убедился что моя идея рабочая https://pastebin.com/uWnsdikr
    
    Sergey_Kovalenko
    14.06.2022 20:43
    #24437920
    Да, я как-то не заметил: вы "энтропию" текста делите на количество "слов" в нем. Для больших текстов разве не будет наблюдаться тенденции к измельчению "слов", чтобы увеличить делитель большого слагаемого?
    
    gchebanov
    14.06.2022 20:58
    #24437948
    $text = \{word_i\};$ $H(text) = \sum_{i}-log(P(word_i))=$ $=\sum_{w,cnt_w} -cnt_w \times log(\frac{cnt_w}{n}) = n \times log(n) - \sum_{w,cnt_w}{cnt_w \times \log(cnt_w)}$
    Я нигде ничего не делю, энтропия считается для всего текста. Если его сжать арифметическим кодеком приложив частотный словарь слов, то ровно столько бит потребуется для сохранения. Вот со словарем я немного упростил функцию. Как раз наоборот, чем меньше слов, тем меньше энтропия текста (но больше словарь).
    
    Sergey_Kovalenko
    14.06.2022 21:32
    #24438002
    Спасибо за уточнение.
1. Raidenyn
  14.06.2022 17:46
  #24437446
  Можно даже упростить задачу. Взять текст на русском, английском или (не дай бог) немецком языке и удалить все точки. Даже в такой постановке словаря будет недостаточно для восстановления точек.
  
  Можете проверить на таком примере:
  
  "Вы встретили Машу в Москве Маша жила на шоссе Энтузиастов в большом доме"
  1. Sergey_Kovalenko
    14.06.2022 18:04
    #24437508
    Почему вы думаете, что разбить на предложения проще, чем на слова?
    
    Raidenyn
    14.06.2022 19:56
    #24437814
    Как минимум потому, что мы имеем очевидные подсказки для возможных расположений точек: конец строки или большая буква в следующем слове.
    
    Для разделения потока символов на слова у нас даже этого нет.
    
    Sergey_Kovalenko
    14.06.2022 20:04
    #24437832
    Так вроде точки вы предложили удалить. Я предлагаю еще большие буквы маленькими сделать. Разумеется 100 процентной точности не требуется. Мне почему-то кажется, что в такой постановке сложность разделения на предложения тоже будет соизмеримой, если не сложнее задачи разделения на слова.

satviewer
14.06.2022 10:45
#24435826
-1
При перестановкЕ! Не И, пожалуйста поправьте.

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

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