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

[Kostia]

Сообщение от s-andriano

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

Правильная строка: MEAN
Варианты с ошибками (50% ошибок):
MAN      EN
QPARK   MEHTAN
TMEAN   MEAN
MFBJN   ZUAN
EOMAN  MEAN

Медиана (LD): MEAN
Обобщенная медиана (LD): MEAN
Медиана (F D): MEAN
Обобщенная медиана (F D): MEAN

Правильная строка: HELSINKI
Варианты с ошибками (50% ошибок):
HLSQPKPK     HOELSVVKIG
THELSIFBJI    HELSSINI
EOMLSNI       DHELSIRIWKJII
HEHTLSINKI  QHSELINI
ZULSINKI      EVSDNFCKVM
Медиана (LD):                   HELSINI
Обобщенная медиана (LD): HELSINKI
Медиана (F D):                  HELSINI
Обобщенная медиана (F D):HELSINI

Источник

Статью я полностью уже переписал, сейчас доделываю практические пример.
Конкретно:
Была разработана некоторая площадка для тестов в виде сайта. На сайте есть просмотр и админка. В админке можно добавлять стать в просмотре их просматривать.
Реализован нечеткий поиск в заголовках статей.
Ждет. Реализация поиска возможных мест внутри статьи которые могли бы ссылаться на уже имеющиеся стать на сайте. Например, есть у нас кулинарный сайт со статьями. Допустим у нас есть статья про сыр и какой то рецепт или еще одна статья где слово сыр упоминается, то программа(при желании) автоматически делает ссылку на имеющуюся статью про сыр при сохранении/редактировании статьи, где про сыр упоминается.
Ждет. Нечеткий поиск внутри статьи.(да и внутри любого большого документа) Задача решить проблему опечаток, пропуска слов в искомой фразе и перестановку слов местами.

[s-andriano]

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

Код:

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

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

Я рассчитывал найти некоторые строковые алгоритмы для практического применения, но там голая теория.

Вот ведь интересно, Utkin хотел найти в статье практику, но не нашел (правда, решил, что в статье имеется теория, которая ему не интересна).
Я, наоборот, хотел найти в статье теорию. Но ... тоже не нашел.
Интересно, что же в статье было?


Ладно, посмотрим, что будет после переделки.

[Kostia]

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

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

Уж и не знаю как еще объяснить.

И еще, выложу что уже написал, просьба покритиковать если не сложно.

[s-andriano]

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

[s-andriano]

По поводу статьи:

1. Вычитать орфографию и пунктуацию.
2. Отсутствует определение расстояния Хемминга. Сильное подозрение, что в (1) смешаны в кучу условие и результат.
3. Правильно ли я понимаю, что расстояние между гистограммами отличается от расстояния между неупорядоченными наборами только метрикой, а в силу произвольности выбора метрики - РМНН - частный случай РМГ?
4. Очень хотелось бы, чтобы определения вводились одним и тем же способом. А то часть - формулами, часть - алгоритмом, часть - вообще отсутствует.
5. Статья по-прежнему посвящена исключительно метрике Левенштейна, к которой в начале зачем-то приведены неполные и разнородные определения других метрик без каких-либо характеристик, описаний достоинств и недостатков и сравнительного анализа.
6. Я так понимаю, сами разделы "Сравнение" и "Применение", а также все разделы, которые планируется разместить между ними, а также разделы после "Применение" еще не дописаны?

[Kostia]

Если у нас есть некоторое множество, и мы рассматриваем именно его, это автоматически означает, что ничего кроме элементов этого множества у нас нет.
Тогда что же именно может быть обобщенной медианой?

Тут моя оплошность. Мы работаем с множеством всевозможных комбинаций символов, где каждый набор символов принадлежит этому множеству. Все это множество можно проецировать на плоскость. Например так:
Возьмем в качестве центра пустую строку(пустой список, набор символов ...) а все остальные расположим в соответствии с расстоянием(расстояние Левенштейна, или просто по кол-ву символов) от центра, это будет радиус, а угол будет меняться от 0 до 2*pi с шагом 1 / (!lenght)(1 / факториал длины набора). Т.е. если представить, то в первом от центра круге, будет алфавит, а дальше все возможные комбинации наборов разной длины из элементов этого алфавита. И мы работаем c подмножеством этого множества.

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

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

3. Правильно ли я понимаю, что расстояние между гистограммами отличается от расстояния между неупорядоченными наборами только метрикой, а в силу произвольности выбора метрики - РМНН - частный случай РМГ?

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

6. Я так понимаю, сами разделы "Сравнение" и "Применение", а также все разделы, которые планируется разместить между ними, а также разделы после "Применение" еще не дописаны?

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

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

[Kostia]

Уф. Отстрелялся. Даже попал в тройку лидеров на факультете. =) Делюсь презентацией: http://prezi.com/dq8amaj2xiky/neurot...c=ref-26645919
Готов ответить на вопросы по презентации, т.к. многие моменты там не освещены, они были просто проговорены.

[Kostia]

Что-то меня этой ночь на подвиги потянуло =)

На скрине пример программы которая осуществляет поиск по словарю и в качестве меры сравнения используется расстояние Левенштейна + некоторые модификации.
Я в поле ввел слово "пятдьест" т.е. допустил 2 ошибки, транспозиция и удаление символа. Довольно таки частые ошибки, программа на первое место поставила именно то слово, что я и имел ввиду, даже при условии что используется не взвешенная стратегия сравнивания.
Следующим шагом будет обучение программы, т.е. сбор информации об опечатках и использование этой информации на практике.

________________Пт., 15 февр.________________
Провел небольшую оптимизация алгоритма, ввел операцию дельней перестановки, т.е. транпозиция не только рядом стоящих символов, а через заданное кол-во. Если выставить этот параметр равным 2, то для того же входного значения "пятдьест" получаем:
пятьдесят
пятеро
пятьсот
протест
пятиться
пятка
дядька
портьера
пьеса
пята
потеха