Форум программистов
 
Контакты: о проблемах с регистрацией, почтой и по другим вопросам пишите сюда - alarforum@yandex.ru, проверяйте папку спам! Обязательно пройдите активизацию e-mail.

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

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


Донат для форума - использовать для поднятия настроения себе и модераторам

А ещё здесь можно купить рекламу за 15 тыс руб в месяц! ) пишите сюда - alarforum@yandex.ru

Ответ
 
Опции темы
Старый 05.12.2012, 11:34   #11
Kostia
Профессионал
 
Аватар для Kostia
 
Регистрация: 21.11.2007
Адрес: Томск
Сообщений: 1,691
Репутация: 615

icq: 426824418
По умолчанию

Цитата:
Сообщение от 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
Источник

Статью я полностью уже переписал, сейчас доделываю практические пример.
Конкретно:
Была разработана некоторая площадка для тестов в виде сайта. На сайте есть просмотр и админка. В админке можно добавлять стать в просмотре их просматривать.
Реализован нечеткий поиск в заголовках статей.
Ждет. Реализация поиска возможных мест внутри статьи которые могли бы ссылаться на уже имеющиеся стать на сайте. Например, есть у нас кулинарный сайт со статьями. Допустим у нас есть статья про сыр и какой то рецепт или еще одна статья где слово сыр упоминается, то программа(при желании) автоматически делает ссылку на имеющуюся статью про сыр при сохранении/редактировании статьи, где про сыр упоминается.
Ждет. Нечеткий поиск внутри статьи.(да и внутри любого большого документа) Задача решить проблему опечаток, пропуска слов в искомой фразе и перестановку слов местами.
Kostia вне форума   Ответить с цитированием
Старый 05.12.2012, 18:00   #12
s-andriano
Профессионал
 
Аватар для s-andriano
 
Регистрация: 08.04.2012
Сообщений: 3,230
Репутация: 563
По умолчанию

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

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


Ладно, посмотрим, что будет после переделки.
s-andriano вне форума   Ответить с цитированием
Старый 05.12.2012, 19:53   #13
Kostia
Профессионал
 
Аватар для Kostia
 
Регистрация: 21.11.2007
Адрес: Томск
Сообщений: 1,691
Репутация: 615

icq: 426824418
По умолчанию

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

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

И еще, выложу что уже написал, просьба покритиковать если не сложно.
Вложения
Тип файла: pdf LD.pdf (147.1 Кб, 2 просмотров)

Последний раз редактировалось Kostia; 05.12.2012 в 20:07.
Kostia вне форума   Ответить с цитированием
Старый 07.12.2012, 15:05   #14
s-andriano
Профессионал
 
Аватар для s-andriano
 
Регистрация: 08.04.2012
Сообщений: 3,230
Репутация: 563
По умолчанию

Все равно непонятно.
Если у нас есть некоторое множество, и мы рассматриваем именно его, это автоматически означает, что ничего кроме элементов этого множества у нас нет.
Тогда что же именно может быть обобщенной медианой?
В принципе, мы могли бы определить некоторое множество, а в нем одно или несколько подмножеств, и после этого вводить медиану для данного подмножества как элемент этого же подмножества, а обобщенную медиану - как элемент множества, который не обязательно входит в подмножество.
Но для этого нам принципиально определить не один объект типа множество, а минимум два: множество и его подмножество.
В общем, что-то с чем-то не состыкуется.
s-andriano вне форума   Ответить с цитированием
Старый 07.12.2012, 15:25   #15
s-andriano
Профессионал
 
Аватар для s-andriano
 
Регистрация: 08.04.2012
Сообщений: 3,230
Репутация: 563
По умолчанию

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

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

icq: 426824418
По умолчанию

Цитата:
Если у нас есть некоторое множество, и мы рассматриваем именно его, это автоматически означает, что ничего кроме элементов этого множества у нас нет.
Тогда что же именно может быть обобщенной медианой?
Тут моя оплошность. Мы работаем с множеством всевозможных комбинаций символов, где каждый набор символов принадлежит этому множеству. Все это множество можно проецировать на плоскость. Например так:
Возьмем в качестве центра пустую строку(пустой список, набор символов ...) а все остальные расположим в соответствии с расстоянием(расстояние Левенштейна, или просто по кол-ву символов) от центра, это будет радиус, а угол будет меняться от 0 до 2*pi с шагом 1 / (!lenght)(1 / факториал длины набора). Т.е. если представить, то в первом от центра круге, будет алфавит, а дальше все возможные комбинации наборов разной длины из элементов этого алфавита. И мы работаем c подмножеством этого множества.
Цитата:
5. Статья по-прежнему посвящена исключительно метрике Левенштейна, к которой в начале зачем-то приведены неполные и разнородные определения других метрик без каких-либо характеристик, описаний достоинств и недостатков и сравнительного анализа.
Их не состоятельность предполагалась очевидной в поставленной(точно, нужно еще задачу описать в самом начале и актуальность) задаче. Думаю если их определить достаточно детально и описать достоинства и недостатки по некоторым критериям, то думаю тогда их не состоятельность точно будет очевидной.
Цитата:
3. Правильно ли я понимаю, что расстояние между гистограммами отличается от расстояния между неупорядоченными наборами только метрикой, а в силу произвольности выбора метрики - РМНН - частный случай РМГ?
Нет, в случае с гистограммами, мы получаем n мерные вектора, где n - размер алфавита и дальше можем ввести любую оценку расстояния для вещественных векторов.(направляющие косинусы, векторное произведение, евклидово расстояние ...)
Цитата:
6. Я так понимаю, сами разделы "Сравнение" и "Применение", а также все разделы, которые планируется разместить между ними, а также разделы после "Применение" еще не дописаны?
Да, их собираюсь дописать после того, как закончу реализацию практических примеров.
По остальным пунктам буду стараться и не лениться, но тогда статься сильно разбухнет =)

Спасибо большое, за то что потратили свое время и указали мне в каком направлении двигаться и что исправить.
Kostia вне форума   Ответить с цитированием
Старый 20.12.2012, 13:07   #17
Kostia
Профессионал
 
Аватар для Kostia
 
Регистрация: 21.11.2007
Адрес: Томск
Сообщений: 1,691
Репутация: 615

icq: 426824418
По умолчанию

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

Последний раз редактировалось Kostia; 20.12.2012 в 13:11.
Kostia вне форума   Ответить с цитированием
Старый 15.02.2013, 00:06   #18
Kostia
Профессионал
 
Аватар для Kostia
 
Регистрация: 21.11.2007
Адрес: Томск
Сообщений: 1,691
Репутация: 615

icq: 426824418
По умолчанию

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

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

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

Последний раз редактировалось Kostia; 15.02.2013 в 10:16.
Kostia вне форума   Ответить с цитированием
Ответ

Опции темы

Ваши права в разделе
Вы не можете создавать новые темы
Вы не можете отвечать в темах
Вы не можете прикреплять вложения
Вы не можете редактировать свои сообщения

BB коды Вкл.
Смайлы Вкл.
[IMG] код Вкл.
HTML код Выкл.

Быстрый переход

Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Обработка символьных строк. (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 02:07
подкоректировать.обработка символьных данных и строк felmor Паскаль 1 25.12.2008 20:12


19:55.


Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2019, Jelsoft Enterprises Ltd.

Проекты отопления, пеллетные котлы, бойлеры, радиаторы
интернет магазин respective.ru