Сравнение символьных строк

[Kostia]

Сравнить как далеко друг от друга расположены точки, труда не составляет, но вот посчитать расстояние между символьными строками, вызывают некоторые затруднения. Но умы человечества нашли не мало способов это сделать:
1. Расстояние Хэмминга.
2. Расстояние между неупорядоченными наборами.
3. Расстояние между гистограммами символов.
4. Расстояние максимальной апостериорной вероятности.
5. Расстояние Левенштейна.

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

Хотел приложить свой код, но обнаружил что это +1000 строк кода ) и много весьма специфичных вещей заточенных под мою задачу, да и вдобавок еще не дописанный ))).

[s-andriano]

Тема интересная, но статья разочаровала.
Во-первых, название не соответствует содержанию: статью следовало бы назвать "кое что о дистанции Левенштейна" (или более жестко: "то, что мне на скорую руку удалось найти в И-нете о дистанции Левенштейна"), т.к. кроме нее вообще ничего не рассматривается, а сама дистанция описана крайне фрагментарно. Нет даже ее сравнения ни с одним из других упомянутых в начале статьи расстояний.
В статье в изобилии встречается терминология, значение которой нигде не объясняется. Например, что такое статистически точное расстояние? Или искаженная символьная строка? Кем она искажена, зачем это сделано и по каким формальным признакам можно искаженную строку отличить от неискаженной?
Что такое обощенная медиана текстовой строки?

[Utkin]

Скорее это заготовка статьи, если не обращать внимания на мелкие ошибки и сокращения, то все равно статья не дает полной картины вопроса. Я рассчитывал найти некоторые строковые алгоритмы для практического применения, но там голая теория.

Просто заметил достаточно много проектов, в которых использование приведенных в статье решений было бы неплохо, а в некоторых просто необходимо.

И этого в статье не видно.

[Kostia]

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

Что такое обощенная медиана текстовой строки?

Медианой называется такой объект из набора, сумма расстояний от которой до остальных объектов будет минимальной.
Пример: Есть отрезок образованный двумя точками и есть точка на этом отрезке, то эта точка и будет являться медианой.

Обобщенная медиана это такой объект, сумма расстояние от которой до остальных объектов минимальна.
Пример 1: В случае с отрезком, обобщенной медианой будет точка на середине отрезка.
Пример 2: Есть множество точек расположенных на окружности, то их обобщенная медиана это цент окружности.

Кем она искажена, зачем это сделано и по каким формальным признакам можно искаженную строку отличить от неискаженной?

Намерено в слове было сделано несколько ошибок 3х типов(которые указаны в статье), таких слов(точнее уже наборов символов) несколько, задача восстановить исходное слово, над которым так сильно поизголялись.


PS: раз появились заинтересованные люди, напишу более подробно с практическим примером нечеткого поиска в заголовках записей в программе QSnippets. Правда размер статьи разрастется, сильно.

[s-andriano]

Сообщение от Kostia

Медианой называется такой объект из набора, сумма расстояний от которой до остальных объектов будет минимальной.

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

Пример: Есть отрезок образованный двумя точками и есть точка на этом отрезке, то эта точка и будет являться медианой.

Не удовлетворяет определению: объект, не входящий в множество (набор), не может быть медианой этого множества.
Тут что-то не в порядке либо с определением, либо с примером.

Обобщенная медиана это такой объект, сумма расстояние от которой до остальных объектов минимальна.

И в чем ее отличие от просто медианы?

[Utkin]

Обобщенная медиана это такой объект, сумма расстояние от которой до остальных объектов минимальна.

Тут уже и меня настораживает. Что это еще за объект? Сумма это число, как я понимаю. Или это определение подразумевает возможность хранения элементов суммы в виде одного объекта ввиду того, что они не могут быть сложены арифметически?

[s-andriano]

Увы, автор использует маловразумительную терминологию, но в данном случае противоречия я не вижу.
Пусть объект - кирпич.
Медиана - тот кирпич, сумма расстояний от которого...
Ничто не мешает измерять расстояние числом при том, что кирпич остается кирпичом и не превращается в число.

[Utkin]

Тогда наверно:

Обобщенная медиана это такой объект, сумма расстояние от которого до остальных объектов минимальна.

[s-andriano]

Да, если еще поправить "сумма расстояние" на "сумма расстояний", по-русски должно быть именно так.
Но, учитывая, что мы говорим "[существительное женского рода] это такой [существительное мужского рода]", употребление неверного родового окончания в определении смысла фразы не меняет.

[Utkin]

Ну если читать быстро - меняет