Форум программистов
 

Восстановите пароль или Зарегистрируйтесь на форуме, о проблемах и с заказом рекламы пишите сюда - alarforum@yandex.ru, проверяйте папку спам!

Вернуться   Форум программистов > Клуб программистов > Обсуждение статей
Регистрация

Восстановить пароль
Повторная активизация e-mail

Купить рекламу на форуме - 42 тыс руб за месяц

Ответ
 
Опции темы Поиск в этой теме
Старый 20.11.2012, 22:23   #1
Kostia
Участник клуба
 
Аватар для Kostia
 
Регистрация: 21.11.2007
Сообщений: 1,691
По умолчанию Сравнение символьных строк

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

Хотел приложить свой код, но обнаружил что это +1000 строк кода ) и много весьма специфичных вещей заточенных под мою задачу, да и вдобавок еще не дописанный ))).
Вложения
Тип файла: pdf LD.pdf (110.5 Кб, 25 просмотров)
Kostia вне форума Ответить с цитированием
Старый 26.11.2012, 23:03   #2
s-andriano
Старожил
 
Аватар для s-andriano
 
Регистрация: 08.04.2012
Сообщений: 3,229
По умолчанию

Тема интересная, но статья разочаровала.
Во-первых, название не соответствует содержанию: статью следовало бы назвать "кое что о дистанции Левенштейна" (или более жестко: "то, что мне на скорую руку удалось найти в И-нете о дистанции Левенштейна"), т.к. кроме нее вообще ничего не рассматривается, а сама дистанция описана крайне фрагментарно. Нет даже ее сравнения ни с одним из других упомянутых в начале статьи расстояний.
В статье в изобилии встречается терминология, значение которой нигде не объясняется. Например, что такое статистически точное расстояние? Или искаженная символьная строка? Кем она искажена, зачем это сделано и по каким формальным признакам можно искаженную строку отличить от неискаженной?
Что такое обощенная медиана текстовой строки?
s-andriano вне форума Ответить с цитированием
Старый 26.11.2012, 23:19   #3
Utkin
Старожил
 
Аватар для Utkin
 
Регистрация: 04.02.2009
Сообщений: 18,136
По умолчанию

Скорее это заготовка статьи, если не обращать внимания на мелкие ошибки и сокращения, то все равно статья не дает полной картины вопроса. Я рассчитывал найти некоторые строковые алгоритмы для практического применения, но там голая теория.
Цитата:
Просто заметил достаточно много проектов, в которых использование приведенных в статье решений было бы неплохо, а в некоторых просто необходимо.
И этого в статье не видно.
Маньяк-самоучка
Utkin появился в результате деления на нуль.
Осторожно! Альтернативная логика
Utkin вне форума Ответить с цитированием
Старый 27.11.2012, 10:31   #4
Kostia
Участник клуба
 
Аватар для Kostia
 
Регистрация: 21.11.2007
Сообщений: 1,691
По умолчанию

Радует что хоть кто-то прочил. Действительно, я совершенно не парился на счет составления статьи, будет свободное время напишу более подробно и развернуто, а пока только ссылки на источники, где можно получить более подробную информацию.
Цитата:
Что такое обощенная медиана текстовой строки?
Медианой называется такой объект из набора, сумма расстояний от которой до остальных объектов будет минимальной.
Пример: Есть отрезок образованный двумя точками и есть точка на этом отрезке, то эта точка и будет являться медианой.

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

Цитата:
Кем она искажена, зачем это сделано и по каким формальным признакам можно искаженную строку отличить от неискаженной?
Намерено в слове было сделано несколько ошибок 3х типов(которые указаны в статье), таких слов(точнее уже наборов символов) несколько, задача восстановить исходное слово, над которым так сильно поизголялись.


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

Последний раз редактировалось Kostia; 27.11.2012 в 10:40.
Kostia вне форума Ответить с цитированием
Старый 02.12.2012, 22:47   #5
s-andriano
Старожил
 
Аватар для s-andriano
 
Регистрация: 08.04.2012
Сообщений: 3,229
По умолчанию

Цитата:
Сообщение от Kostia Посмотреть сообщение
Медианой называется такой объект из набора, сумма расстояний от которой до остальных объектов будет минимальной.
Было бы лучше, если бы это было в статье.
Но лучше пользоваться стандартной терминологией.
Либо определить, что такое набор и чем он отличается от множества.
Цитата:
Пример: Есть отрезок образованный двумя точками и есть точка на этом отрезке, то эта точка и будет являться медианой.
Не удовлетворяет определению: объект, не входящий в множество (набор), не может быть медианой этого множества.
Тут что-то не в порядке либо с определением, либо с примером.
Цитата:

Обобщенная медиана это такой объект, сумма расстояние от которой до остальных объектов минимальна.
И в чем ее отличие от просто медианы?
s-andriano вне форума Ответить с цитированием
Старый 03.12.2012, 10:26   #6
Utkin
Старожил
 
Аватар для Utkin
 
Регистрация: 04.02.2009
Сообщений: 18,136
По умолчанию

Цитата:
Обобщенная медиана это такой объект, сумма расстояние от которой до остальных объектов минимальна.
Тут уже и меня настораживает. Что это еще за объект? Сумма это число, как я понимаю. Или это определение подразумевает возможность хранения элементов суммы в виде одного объекта ввиду того, что они не могут быть сложены арифметически?
Маньяк-самоучка
Utkin появился в результате деления на нуль.
Осторожно! Альтернативная логика
Utkin вне форума Ответить с цитированием
Старый 03.12.2012, 15:13   #7
s-andriano
Старожил
 
Аватар для s-andriano
 
Регистрация: 08.04.2012
Сообщений: 3,229
По умолчанию

Увы, автор использует маловразумительную терминологию, но в данном случае противоречия я не вижу.
Пусть объект - кирпич.
Медиана - тот кирпич, сумма расстояний от которого...
Ничто не мешает измерять расстояние числом при том, что кирпич остается кирпичом и не превращается в число.
s-andriano вне форума Ответить с цитированием
Старый 03.12.2012, 19:04   #8
Utkin
Старожил
 
Аватар для Utkin
 
Регистрация: 04.02.2009
Сообщений: 18,136
По умолчанию

Тогда наверно:
Цитата:
Обобщенная медиана это такой объект, сумма расстояние от которого до остальных объектов минимальна.
Маньяк-самоучка
Utkin появился в результате деления на нуль.
Осторожно! Альтернативная логика
Utkin вне форума Ответить с цитированием
Старый 04.12.2012, 16:23   #9
s-andriano
Старожил
 
Аватар для s-andriano
 
Регистрация: 08.04.2012
Сообщений: 3,229
По умолчанию

Да, если еще поправить "сумма расстояние" на "сумма расстояний", по-русски должно быть именно так.
Но, учитывая, что мы говорим "[существительное женского рода] это такой [существительное мужского рода]", употребление неверного родового окончания в определении смысла фразы не меняет.
s-andriano вне форума Ответить с цитированием
Старый 04.12.2012, 17:20   #10
Utkin
Старожил
 
Аватар для Utkin
 
Регистрация: 04.02.2009
Сообщений: 18,136
По умолчанию

Ну если читать быстро - меняет
Маньяк-самоучка
Utkin появился в результате деления на нуль.
Осторожно! Альтернативная логика
Utkin вне форума Ответить с цитированием
Ответ


Купить рекламу на форуме - 42 тыс руб за месяц

Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Обработка символьных строк. (TurboC++) flamen1003 Помощь студентам 0 24.04.2012 01:07
Обработка Символьных Строк неоспоримый Помощь студентам 2 01.04.2012 21:04
Обработка символьных строк.Шифровка перестановками.Паскаль. Lerika Lover Помощь студентам 0 28.12.2011 15:37
Обработка символьных строк 1OffSide Общие вопросы C/C++ 1 21.12.2010 01:07
подкоректировать.обработка символьных данных и строк felmor Паскаль, Turbo Pascal, PascalABC.NET 1 25.12.2008 19:12