Вхід і реєстрація
Розробка · 25 жовтня 2009, 11:53 972
alan-bradley.livejournal.com

Нечеткий поиск

Підписуйтеся на Telegram-канал «DOU #tech», щоб не пропустити нові технічні статті.

День добрый.

Возникла задача реализовать нечеткий поиск слов русского языка — при этом учитывать

1. Похожесть букв (т.е., например, расстояние между «д» — «т» меньше, чем между «д» и «у» )

2. Возможные пропуски \ лишние буквы

3. Перестановки букв ( «НИШПУК» — «ПУШКИН» )

Иными словами, на входе имеем два слова, на выходе — расстояние между ними с учетом вышеперечисленного.

Может, кто-нибудь с подобным сталкивался? Посоветуйте литературу (желательно — в форме статей)

Спасибо.

👍ПодобаєтьсяСподобалось0
До обраногоВ обраному0
LinkedIn
Дозволені теги: blockquote, a, pre, code, ul, ol, li, b, i, del.
Ctrl + Enter
Дозволені теги: blockquote, a, pre, code, ul, ol, li, b, i, del.
Ctrl + Enter
Sergiy Matusevych вечный чайник 29.10.2009 20:09

alan-bradley.livejournal.com:, а вопрос еще актуален? есть какие-то решения/предложения/вопросы?

Відповісти
Підтримати
anonymous 28.10.2009 22:33
ВТФ индикаторный кубит?
< matan> Для квантовой машины Тьюринга не только остается справедливой пресловутая Entscheidungsproblem, но и появляется дополнительное естественное осложнение: КК не должен наблюдаться до полного завершения цикла вычислений. Но так как мы: 1) заменяем каждый классический бит строго обратимым квантовым гейтом, вводя тем самым дополнительные кубиты, 2) избегаем операций копирования ввиду нелинейности классического оператора копирования, — можно выбрать один из этих автоматически вовлекаемых в работу программы мусорных кубитов за индикаторный и приказать КК устанавливать его, скажем, в 1, когда программа останавливается в 1, и в 0 в остальных случаях. Этот кубит мы будем наблюдать периодически, разрушая его локальную когерентность с рабочими регистрами, но не воздействуя на кубиты, непосредственно задействованные в поиске по Гроверу. </matan>

PS. Уважаемые тролли, вместо чтения информации, помещенной под тегом «матан», пожалуйста, проследуйте по той же ссылке, что и plochish.

Відповісти
Підтримати
anonymous 28.10.2009 21:06
Но можно пруфлинк на то как «обращали» квантовую машины Тьюринга используя этот парадокс?

Трюк входит в оригинальную статью Шора по алгоритму взлома RSA на КК (Квантовый компьютер и квантовые вычисления, выпуск 2 под ред Садовничего, 1999, с. 217−219). Пиши в личку, поищу текст.

ты что то отличное от обсуждаемого в этой ветке нечеткого поиска имеешь ввиду?

Ссылки иллюстрируют принципиальную возможность реализации алгоритмов семейства Гровера на QPL.

Відповісти
Підтримати
crypto5 28.10.2009 19:11

2crypto5 — проблема полноты не есть P0 для поисковой машины, скорее проблема качества, закон Бретфорда (Bradford) говорит что нет смысла гоняться за полнотой, достаточно выбирать изюминки:)

Консенсус не достигнут.

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

Она не завязана на индекс яху.

Відповісти
Підтримати
junior dev 28.10.2009 18:50
2crypto5 — проблема полноты не есть P0 для поисковой машины, скорее проблема качества, закон Бретфорда (Bradford) говорит что нет смысла гоняться за полнотой, достаточно выбирать изюминки:)

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

Відповісти
Підтримати
Sergiy Matusevych вечный чайник 28.10.2009 18:35

junior_dev:

постесняюсь спросить, не ужто вы перебором обошли все страницы форума? или как-то хитрее?

да нет, на самом деле все очень тупо:) сначала обошел страницы /forum/page/ (\d+), и через YQL вытащил список тем — там в последней колонке, «Свежесть», стоит ссылка на последнее сообщение в треде, в формате /forum/topic/ (\d+) (?:/page/ (\d+)) #post- (\d+), т.е. сразу можно прикинуть, в какой теме сколько страниц. ну, а дальше немного BeautifulSoup-a, и золотой ключик у нас в кармане:) собственно, все и началось с того, что я баловался с BeautifulSoup-ом, а developers.org.ua у меня давно уже служит полигоном для подобных экспериментов.:) весь код — 85 строк, 4 часа работы:) если интересно, могу выложить куда-нибудь, но там все грязно и не очень интересно., а марковские цепи я вчера на коленке сбацал по приколу, чтобы для хелипа сингулярность наступила поскорее:)

Відповісти
Підтримати
Sergii Voloshyn Product Manager в DOU.ua 28.10.2009 18:09

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

Кажется исправил — теперь не введя никаких данных ничего не получится запостить:) Еще удалил поле email, оставил только капчу и имя. И добавил JS проверку пустых полей.

Відповісти
Підтримати
crypto5 28.10.2009 17:54

не хочу никого обидеть, но врядли Гугль стараеться покрыть ДОУ по максимуму:)

Это одна из их основных целей — максимально покрыть интернет и ДОУ в частности.

Відповісти
Підтримати
junior dev 28.10.2009 17:46

не хочу никого обидеть, но врядли Гугль стараеться покрыть ДОУ по максимуму:)

Відповісти
Підтримати
Sergii Voloshyn Product Manager в DOU.ua 28.10.2009 17:36
2junior_dev, да, я протупил.
Если бы я делал, то перебирал что-то типа результатов гугла site: developers.org.ua/forum/topic

Минусы что совсем новых нет, но зато проще выбрать все ссылки и нагрузка, но ДОУ меньше:)

Відповісти
Підтримати
junior dev 28.10.2009 17:25
как я сказал дажее идем по страницам пока не получим ответ сервера — страницы нет, что-то типа 404...
вот например
for (size_t topicId = 0; topicId < = MaxExtractedId /*получаем найдя последнюю тему*/; topicId ++)
for (size_t page = 0; page < = (size_t) −1/*можно идти до посинения пока сервер страницами кормит, один облом можно нарваться на редирект, но тогда либо ставим лимит и тут либа улучшаем кроулер*/; page++)
{
if (2**! = CrawlPage (topicId, page))
break;

}

Відповісти
Підтримати
Sergii Voloshyn Product Manager в DOU.ua 28.10.2009 17:17
2junior_dev:, но в каждой теме еще может быть несколько страниц, там тоже границу брать?:)

2Oleksandr Tymoshenko: спасибо, постараюсь исправить

Відповісти
Підтримати
junior dev 28.10.2009 17:13
2hellip вообще-то я никакой статистики не приводил, а вот как раз motus для внешнего ресурса выдал очень клевую и точную статистику...
постесняюсь спросить, не ужто вы перебором обошли все страницы форума? или как-то хитрее?

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

Відповісти
Підтримати
crypto5 28.10.2009 15:23

До 100% тоже можем. Есть такая штука — квантовый эффект Зенона называется. Она в этой задаче тоже возникает, потому что квантовая машина Тьюринга работает обратимо, и мы можем сжульничать — посмотреть, действительно ли получается ноль или единица, в тот самый момент, когда мы ожидаем, что должен получиться ноль или единица. Если этот фокус повторять достаточно долго, можно запереть систему в нужном состоянии с вероятностью 1.

Что такое парадокс Зенона я знаю. Но можно пруфлинк на то как «обращали» квантовую машины Тьюринга используя этот парадокс?

При этом в работу самих квантовых регистров мы не вмешиваемся. Мы смотрим только на состояние индикаторных кубитов (garbage).

ВТФ индикаторный кубит?

Однако если уж мы плавно перешли к квантовой информатике, то написать программу нечеткого поиска для КК в принципе возможно (см. sneezy.cs.nott.ac.uk/qml и ссылки там, а также arXiv: quant-ph/9708016), и более того, она в отличие от алгоритма Дойча-Джозса даже имеет практическую ценность (прогоняли на сверхпроводниковых восьмикубитовых вариантах КК).

Как то не нашел по обоим ссылкам ничего про нечетный поиск. Или ты что то отличное от обсуждаемого в этой ветке нечеткого поиска имеешь ввиду?

Відповісти
Підтримати
Sergiy Matusevych вечный чайник 28.10.2009 15:10

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

Відповісти
Підтримати
Sergii Voloshyn Product Manager в DOU.ua 28.10.2009 15:08

Да, просто как я понял, мерялись кол-вом сообщений на форуме.

Відповісти
Підтримати
crypto5 28.10.2009 13:13

Я только уточнил запросы из поста о гугле:

www.developers.org.ua/...ge/3#post-14835

Уточнение получилось совсем в неправильную сторону, так как Motus активно светился в коментариях к статьям.

Відповісти
Підтримати
anonymous 28.10.2009 09:53

2 Сергей Волошин Спасибо, ссылка в письме зачетная. *стисняюс*

Так как тут часто упоминаються японские авторы (эти символы пришли ко мне из японии):) да и просто разбавить ваши измерения достоинств
junior_dev, вы как всегда правы. По материалам топика уже можно писать небольшую статью в Journal of Theoretical and Applied Phallometry.
ЗЫ. Я восхищен вашей статистикой. Мы посрамили специалистов *YAHOO*.
2 plochish
Вот здесь ты найдешь пример кода, который можешь использовать на собеседовании:

research.sputtv.com/news/1557.html

Відповісти
Підтримати
Sergii Voloshyn Product Manager в DOU.ua 28.10.2009 06:58

Посмотри-ка пост Волошина выше, потом будешь трендеть.

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

Я только уточнил запросы из поста о гугле:
www.developers.org.ua/...ge/3#post-14835
Кстати прикрутил только что плагин статистики, он только залогиненных считает правда:

www.developers.org.ua/...view/statistics

Відповісти
Підтримати
junior dev 28.10.2009 04:13
Господа, азиа-веды, а вы не замечали что SortedDictionary, тот что в дот-нете не правильно сортирует для азиатских языков у него почему-то слово 00E3 82A4 младше чем 00E3 818F.

Так как тут часто упоминаються японские авторы (эти символы пришли ко мне из японии):) да и просто разбавить ваши измерения достоинств;)

Відповісти
Підтримати
anonymous 28.10.2009 01:25
Eще! Eще!
[сидит и ждет]

ЗЫ Пора уже проверять как хорошо у хулипа кепка на голове держиться

Відповісти
Підтримати
anonymous 28.10.2009 01:08

требую продолжения банкета

Відповісти
Підтримати
anonymous 27.10.2009 23:39

< repeat> Придется тебя тупо игнорить. </repeat>

Відповісти
Підтримати
Sergiy Matusevych вечный чайник 27.10.2009 23:33
408 hellip
Посмотри-ка пост Волошина выше, потом будешь трендеть.

учимся сначала думать, а потом молчать, окей? похоже, Волошин учитывал страницы, а не сообщения, и только от залогиненного пользователя: 

sqlite> SELECT count(p.msg), u.profile_id > 0, u.name FROM post p
  JOIN user u ON (p.user_id = u.id) WHERE u.name LIKE '%hellip%' GROUP BY 2,3 ORDER BY 1 DESC;
271   1   hellip
137   0   hellip
1     0   2  hellip

Ты всего лишь работаешь на них. «Из-за бугра повякивать — много ума не нужно…"©

типа — «ты чьих будешь? ", ага. так важно разобраться, кто чей холоп, а кто барин? вот она, пиндосия в голове. тьфу, мерзость.
Відповісти
Підтримати
anonymous 27.10.2009 23:02

site: developers.org.ua/forum
163/39 = 4.18

Не совсем корректно. Это количество страниц. На одной странице может быть больше одного сообщения от участника.

Відповісти
Підтримати
anonymous 27.10.2009 22:45
408 hellip

Посмотри-ка пост Волошина выше, потом будешь трендеть.

вот, с пылу, с жару:
$./hellchat.py hellip 2 100

Чувствую, сегодняшняя порция работы над скрейпером основательно выела твой моск. Мне тебя жаль. Ничто не предвещало.: DDD ((

37 лет? олдфаг! работает в большой компании? планктон! живет в америке? пиндос!
Где в моем посте слово «планктон»? Опять фрейдистская оговорка... LOL
Кроме того, я не писал, что ты пиндос. ^_^ ^_^ Ты всего лишь работаешь на них. "Из-за бугра повякивать — много ума не нужно..."©
Олдфаг — по идее, уважительная оценка, учи матчасть и сетевой фольклор.
Исходную задачку мне решать не слишком интересно, я просто кинул пару поленьев в общую топку, и если бы тебя не понесло в пим дырявый, то этим дело бы и ограничилось.
Ладно, подведем итоги. Ты одним этим топиком наработал на хороший, долгий бан, но тролли вроде тебя опасны тем, что за ними легко улететь и самому. Однако корявый и глючный плагин форума не позволит провести эффективный экстерминатус зарвавшегося йеху-девелопера. Придется тебя тупо игнорить. "Буду пытаться контролировать свои эмоции, но вдруг они меня выведут, — я же не могу сказать, как я буду себя вести, если буду вспыльчив, проведу я серию ударов или нет. Если проведу — им будет плохо, поэтому пусть будут повнимательнее, профессиональными и честными."©
Adios, pendejo. Yo.

Ты живешь неподалеку от мексиканской границы, поэтому, надеюсь, способен понять этот месседж.

Відповісти
Підтримати
junior dev 27.10.2009 22:34

2motus ооо! клева, а можно дистрибьюшен по среднему числу постов за день:) ато как-то многовато для меня выходит:) не думал что я такой социальный

Відповісти
Підтримати
Sergiy Matusevych вечный чайник 27.10.2009 22:29

hellip:

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

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

Во-вторых, если ты не можешь или не хочешь разобраться в этом, то я тебе не доктор.

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

Я про твой переезд в Америку и интеграцию в тамошнюю корпоративную систему. Ты там, если верить линкедину, еще и четырех лет не проработал, а уже повадился класть с прибором на всех, кто не согласен вести разговор в удобных тебе выражениях.
вот тебе америка покоя не дает! так нет, нужно влезть ко мне в профайл и понавешивать ярлыков. 37 лет? олдфаг! работает в большой компании? планктон! живет в америке? пиндос! etc. etc. сорри, но это и вправду ни разу не удобные для меня выражения — это хамство, и ничего больше.

ЗЫ тебе, похоже, очень удобно делить собеседников на «своих» и «пиндосов»., а граница эта — у тебя, дружок, в голове.

ты в курсе, что за пару месяцев пребывания на форуме ты уже вышел в top5 по количеству постов — это включая хозяев сайта и анонима?
Да? И откуда ты взял эту статистику? У меня в профиле, на всякий случай, такого и близко нет.

да я тут провожу небольшой социологический эксперимент:) вчера вечером написал скрейпер для форума, и ночью стянул все посты: 

sqlite> SELECT count(p.msg), u.name FROM post p
  JOIN user u ON (p.user_id = u.id) GROUP BY 2 ORDER BY 1 DESC LIMIT 10;
763     Аноним
688     Сергей Волошин
486     eugene_n
486     junior_dev
408     hellip
309     Mike Gorchak
290     Макс Ищенко
262     sashaeve
245     vkozhaev
216     crypto5

Прикинул. Посчитал. Остался вполне так себе доволен результатом. Тем более я рассчитываю дожить до Сингулярности.
сингулярность - это момент, когда интеллект машины сравняется с интеллектом человека? тогда поздравляю, для тебя она уже наступила :)

вот, с пылу, с жару:

$ ./hellchat.py hellip 2 100
возможно, для всей известной Вселенной. При этом в работу самих квантовых
регистров появляется состояние |FAIL>. В этом случае инвестиции делать не
следует, поскольку о значении функции G(f), появляется с вероятностью 1. При
этом в работу самих квантовых регистров мы не вмешиваемся. Мы смотрим только на
состояние индикаторных кубитов (garbage). Нет, я так и сказал несколькими
постами выше: факториальное потребление памяти, число вариантов растет
пропорционально количество перестановок. Особенно если квадратно-гнездовым
методом загрузить все варианты в степени маразма собеседующего. Если вы шарите
в рабочем языке, могут сделать поблажку. Однако см. п. 1. Лично я терпеть не
могу двумерных игрушек, хотя и понимаю,

: -)
Відповісти
Підтримати
anonymous 27.10.2009 22:29

junior_dev, +100. А он мне и не нужен, топ-5. Это мотуз тут разошелся, флеймя с самим собой. Сейчас вышло новое русское издание Нила Геймана, American Gods, там цитируется один замечательный стишок, увиденный главным героем в общественном транспорте. Я бы его тут процитировал, описывая поведение мотуза, но меня за это немедленно забанят, поэтому напишу в личку.

Відповісти
Підтримати
junior dev 27.10.2009 22:17
для получения Top5 Гугля не достаточно, если конечно не пытаться перебрать всех юзеров:)
в любом случае, зачем на человека накидываться если он высказал свое мнение и поделился информацией которой он распологает?

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

Відповісти
Підтримати
anonymous 27.10.2009 22:15
Ура. Спс. Но это все равно меньше 10.

В профиле мотуса, однако, стоит 27 вместо 39.

Відповісти
Підтримати
anonymous 27.10.2009 22:08
Если тупо взять отношение ссылок, найденных Гуглом, получим
hellip/motus = 206/108 = 1.91.
Это несколько меньше 10.

ЗЫ. Еще раз — хелл-ай-пи. Ай-пи фром хелл.

Відповісти
Підтримати
crypto5 27.10.2009 21:55
junior_dev
Моя оценка объективной реальности подсказывает мне что он этого не делал.
На самом деле приблизительную оценку соотношения количества тем, в которых участвовал Хелип и Мотус можно получить с помощью запросов к гуглу:
www.google.com/search q=motus+site%3Adevelopers.org.ua

www.google.com/search q=hellip+site%3Adevelopers.org.ua

Відповісти
Підтримати
anonymous 27.10.2009 21:46
Да, мощная технология разработана мотузом, нет слов. Результат выполнения процитированного запроса таков:
select a.content, p.content from html where url=’www.developers.org.ua/members and xpath=’//div [@class= «members» ] /ul/li

дает на выходе 

true7347283559Python— Разработка на языке Python.Стартапы— Winner takes it all. Создаем онлайн-проекты, нацеленные на быстрый успех.Java— Новости Java технологийФункциональное программирование— Лента блогов о функциональной парадигме программирования. Haskell, Lisp, Scala, Groovy, Smalltalk,F#, etc.Zend Framework— Статьи, переводы, советы, ссылки и мнения о Zend Framework.Средства разработки— Инструменты для разработки, тестирования кода, управления проектами.Embedded— Разработка встроенных систем.Планетарий ДОУ— Для тех, кто не хочет вешать на себя ярлык какого-либо сообщества. Для тех кто стремиться писать на различные IT-шные и не только темы, не загоняя себя в жесткие рамки других сообществ.Mobile Development— Программирование для мобильных устройств. Разработка для Windows Mobile, Windows CE, Google Android, iPhone, Symbian, Palm WebOS и др.За жисть— всякое разное, не только айтишное. где-то такУправление— всякое управление. проектами, персоналом, требованиямиAdobe Flash Platform— Разработка приложений с использованием технологий Adobe и на основе Adobe Flash Platform. Создание Flash/Flex RIA-приложений, интеграция с серверной платформой Adobe Coldfusion и другими. Использование средств разработки Adobe: Flash, Flash Builder, Photoshop, Catalyst, Coldfusion Builder и др..ua-нетИгорь Хоменко— студентДмитрий Ляш— программист, ПриватбанкAlex Zasikan— C++ developerYaroslav Vorozhko— Создаю веб-проекты с PHP, ZF, MySQL и SphinxDmitry UtkinАлександрАртем Ильин— SQ Engineer, Sun MicrosystemsЮра Халяпин— Сборщик Пк, Кпи-СервисAnatoliy Loyko— VLFNAndrey Borovskiy— mangr, Innovative Solution

Няка.

И что, ты думаешь Мотус таким образом собрал статистику постов Хелипа?

Вот упрямый задрот...© Почитал я, однако, вышецитированный блог и увидел, что мотуза и раньше, еще до моего пришествия на сайт, волновали вопросы, адекватно ли его из-заокеанское восприятие киевской реальности:

Меня, кстати, напрягают такие ярлыки: «уехал» (еще лучше — «свалил», «эмигрировал», «покинул родину») — значит, «не наш»; объективности от такого кадра ждать не приходится . Аналогично, те, кто использует свои институтские знания в работе — «эльфы», и их единицы. Ну блииин. Ребята, да с вашей профессией можно работать где угодно. Само понятие «уехать» теряет смысл. Из Житомира в Киев — это «свалить»? Нет? А в Москву? А в Прагу? Где начинается это «свалить»?

Полезная вещь — фрейдистские оговорки.

ЗЫ. Мой ник читается так: хелл-IP.

Відповісти
Підтримати
junior dev 27.10.2009 21:35
почему бы и нет:) это же очень легко, единствнный баг который может быть в вычислениях это то что нет гарантии что Yahoo проиндексировал все страницы форума
и поэтому стастика может быть не верной, но если у кроулера Яху равномерное распределение индекса для страниц одного форума (нет к примеру ранжирования по популярности) то тогда страницы должны равномерно отсутсвовать и поэтому можно считать выборку чесной, например эта тема не проиндексирована:)
siteexplorer.search.yahoo.com/search p=www.developers.org.ua/...topic/1141& y=Explore+URL& fr=sfp,
а Гугль молодец:)

www.google.com/search hl=en& safe=off& q=site%3Ahttp%3A%2F%2Fwww.developers.org.ua%2Fforum%2Ftopic%2F1141& aq=f& oq=& aqi=

Відповісти
Підтримати
crypto5 27.10.2009 21:01

junior_dev

И что, ты думаешь Мотус таким образом собрал статистику постов Хелипа?

Відповісти
Підтримати
junior dev 27.10.2009 20:34

Да? И откуда ты взял эту статистику? У меня в профиле, на всякий случай, такого и близко нет.

www.developers.org.ua/...y-linkdump-178
Yahoo! Query Language — (похожий на) SQL интерфейс к чему угодно на вебе. Особенно удобен, если нужно тянуть данные из нескольких Yahoo! API одновременно. Впрочем, теперь и сторонние сайты могут тоже открывать свои API в виде таблиц YQL (см. YQL Open Data Tables), а YQL Execute позволяет даже выполнять код на JavaScript в запросе. И, конечно, самая красота — это YQL Console, где можно поиграть с данными отовсюду в интерактивном режиме.
Быстрый пример — список новых пользователей DOU:

select a.content, p.content from html where url=’www.developers.org.ua/members and xpath=’//div [@class= «members» ] /ul/li’

Відповісти
Підтримати
anonymous 27.10.2009 19:57
Трохи в сторону від теми та срачу. Який, на думку шановної аудиторії, алгоритм нечётких поисков допоможе чотко прочитати такий текст.
Ну, скжете, боян. А все ж рік назад розбирали якихось нещасних десяток тисяч записів, з пошуком схожих і т.п. Руками набитих за багато років юзерами, в т.ч. неграмотними. Саме скоре (дешеве і якісне) рішення було — наваяти бидлоформочку, там «LIKE» в SQL, і посадити дівчинку.

Зразу ж скажу — перед тим алгоритмів перебрано було багато, хороших та різних. Швидкість була, потрібна якість — ні.

Відповісти
Підтримати
anonymous 27.10.2009 19:41
и разом из уставшего от чайницких вопросов науковця...

Ой, да я ни разу не ученый, боже мой. У меня даже диссера защищенного нет. Мог быть, конечно, да отпал за ненадобностью. А в CS мне в страшном сне не приснится идти. *RTFM*

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

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

и в снисходительном тоне нес всякую околонаучную херню...

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

наверняка, ты про свое появление на этом сайте

Нет, конечно. Я про твой переезд в Америку и интеграцию в тамошнюю корпоративную систему. Ты там, если верить линкедину, еще и четырех лет не проработал, а уже повадился класть с прибором на всех, кто не согласен вести разговор в удобных тебе выражениях.

ты в курсе, что за пару месяцев пребывания на форуме ты уже вышел в top5 по количеству постов — это включая хозяев сайта и анонима?

Да? И откуда ты взял эту статистику? У меня в профиле, на всякий случай, такого и близко нет.

я за все время существования форума написал в 10 раз меньше.

И что это должно означать? Что ты бохъ? Дык я это признал, см. выше.

,
а ты бы, дружок, пораскинул мозгами, и посчитал, сколько тебе еще осталось до долгожданного биологического триумфа.
Прикинул. Посчитал. Остался вполне так себе доволен результатом. Тем более я рассчитываю дожить до Сингулярности.

ЗЫ. Ты первый перешел на личности и начал флеймить. Я на тебя бочку без повода не гнал.

Відповісти
Підтримати
Sergiy Matusevych вечный чайник 27.10.2009 18:37

hellip:

PS. Вообще, подводя итог нашему с motus маленькому флеймику, хочу заметить, что спор с таким закаленным олдфагом, как Сергей, бесспорно, относится к числу наиболее престижных и трудных дисциплин Специальной Олимпиады. Ситуация усугубляется тем, что у некоторых специалистов, выехавших из xUSSR в Пиндосию, возникает непреодолимое желание в свободное от работы время извергнуть с высокой колокольни поток отходов на каждого, кто имел несчастье родиться позже и/или не разделяет мотивов, побудивших упомянутого специалиста податься за океан.

whoa, вот это скачок научной мысли:), а каков язык! олдфаг, пиндосия, эмигрант, xUSSR, спец олимпиада... ты хоть понимаешь, что наверняка не одному мне оскорбительно видеть на форуме такой выхлоп? мда, растопырить пальцы у парнишки не получилось, и тут такая счастливая мысль — заглянуть к оппоненту в профайл и мягко перевести беседу в русло «а ты кто такой? ».

(Это, например, не относится к уважаемым junior_dev и crypto5.)

да, некоторые эмигранты из пиндосии ниче так пацаны.:)

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

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

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

наверняка, ты про свое появление на этом сайте. ты в курсе, что за пару месяцев пребывания на форуме ты уже вышел в top5 по количеству постов — это включая хозяев сайта и анонима? я за все время существования форума написал в 10 раз меньше.

Однако бесспорным является и то, что по статистике, у таких, как я, есть хорошие шансы сохраниться в строю айтишнегов к тому моменту, когда подавляющее большинство сегодняшних олдфагов, активно п****щих остальное «быдло», уже будет нетранспортабельно.

ну что же, если нет надежды на собственные способности, остается уповать на законы природы.:), а ты бы, дружок, пораскинул мозгами, и посчитал, сколько тебе еще осталось до долгожданного биологического триумфа. ну, на сколько лет ты можешь быть меня младше? на 10−12, максимум. допустим, я уйду на пенсию в 60 лет. сколько тебе будет годков к тому времени? 50? ага, то-то развернешься, наконец!

Відповісти
Підтримати
anonymous 27.10.2009 18:22

До 100% тоже можем. Есть такая штука — квантовый эффект Зенона называется. Она в этой задаче тоже возникает, потому что квантовая машина Тьюринга работает обратимо, и мы можем сжульничать — посмотреть, действительно ли получается ноль или единица, в тот самый момент, когда мы ожидаем, что должен получиться ноль или единица. Если этот фокус повторять достаточно долго, можно запереть систему в нужном состоянии с вероятностью 1.

При этом в работу самих квантовых регистров мы не вмешиваемся. Мы смотрим только на состояние индикаторных кубитов (garbage).

аццкая ахинея

Відповісти
Підтримати
anonymous 27.10.2009 17:43

я так понимаю в современной квантовой механике наличие паралельных вселенных совсем необязательно!

Да, это одна из интерпретаций — наряду с копенгагенской, фейнмановской и гейзенберговой.

Что такое операция «—»?

Поразрядное вычитание.

Поэтому без предметного рассмотрения конкретной функции f, данное обсуждение ничего не стоит.

Правильно. Я бы его и не затевал, кабы не придирчивость Матусевича.

Схлопывание состояния произойдет при любом наблюдении, а не обязательно успешном.

Да, конечно.

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

Не спорю.

Но мы можем поднять вероятность до любого желаемого нами уровня (но не до 100%) путем небольшого количества повторяющихся экспериментов.

До 100% тоже можем. Есть такая штука — квантовый эффект Зенона называется. Она в этой задаче тоже возникает, потому что квантовая машина Тьюринга работает обратимо, и мы можем сжульничать — посмотреть, действительно ли получается ноль или единица, в тот самый момент, когда мы ожидаем, что должен получиться ноль или единица. Если этот фокус повторять достаточно долго, можно запереть систему в нужном состоянии с вероятностью 1.

При этом в работу самих квантовых регистров мы не вмешиваемся. Мы смотрим только на состояние индикаторных кубитов (garbage).

А теперь самый главный вопрос который меня беспокоит: я правильно понимаю что ты предложил подход для решения задачи топик стартера, который можно применить только на квантовых компъютерах?
Нет, я всего лишь задался целью доказать Матусевичу, что я не трепло и не верблюд. Если бы он не прицепился к бедолашным япошкам, в чьей книжке действительно есть много полезных алгоритмов, то и на КК разговор бы не съехал.

Однако если уж мы плавно перешли к квантовой информатике, то написать программу нечеткого поиска для КК в принципе возможно (см. sneezy.cs.nott.ac.uk/qml и ссылки там, а также arXiv: quant-ph/9708016), и более того, она в отличие от алгоритма Дойча-Джозса даже имеет практическую ценность (прогоняли на сверхпроводниковых восьмикубитовых вариантах КК).

Відповісти
Підтримати
crypto5 27.10.2009 15:14

Хорошо. Тогда давай будем считать, что в самой первой фразе вместо N вселенных — N состояний квантового компьютера, на котором вычисляются среди прочего значения рекурсивной функции f (i), i = 1,..., N.

С этого нужно было начинать, я так понимаю в современной квантовой механике наличие паралельных вселенных совсем необязательно!

Измерение любого невырожденного наблюдаемого состояния даст один из четырех возможных результатов: |0> = (½) (|0, 0> —|0, 1> +|1, 0> —|1, 1>), |1> = (½) (|0, 0> —|0, 1> —|1, 0> +|1, 1>), |FAIL> = (½) (|0, 0> +|0, 1> +|1, 0> +|1, 1>), |ERROR> = (½) (|0, 0> +|0, 1> —|1, 0> —|1, 1>).
Эти четыре состояния образуют ортонормированное векторное множество.
Что такое операция «—»?

Я так понимаю ты сейчас рассматриваешь примес с двумя кубитами, то есть мы имеем дело с двумерным пространством. Как четыре двумерных вектора могут образовывать ортонормированное множество в двухмерном пространстве, если максимальная размерность ортонормированного множества в двухмерном пространстве может быть 2, и это и будет базис пространства?

Если измерение дало значение с амплитудой 0 или 1, то автоматически и функция стратегии G (f) == f (0) + f (1) или, лучше, G (f) == f (0) XOR f (1) даст значение 0 или 1. Условно можно принять, что если 0 — мы играем на повышение, если 1 — играем на понижение. Как бы там ни было, этот продуктивный результат, дающий возможность построить осмысленную стратегию на основании сведений о значении функции G (f), появляется с вероятностью ½

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

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

Схлопывание состояния произойдет при любом наблюдении, а не обязательно успешном. Принцип квантовых вышислений совсем в другом — мы в любом случае получим результат который правилен только с определенной вероятностью. Но мы можем поднять вероятность до любого желаемого нами уровня (но не до 100%) путем небольшого количества повторяющихся экспериментов.

А теперь самый главный вопрос который меня беспокоит: я правильно понимаю что ты предложил подход для решения задачи топик стартера, который можно применить только на квантовых компъютерах?

Відповісти
Підтримати
anonymous 27.10.2009 12:04

plochish, а вот теперь ты можешь с полным правом убить себя об стену, трусливая} | {о.п.а...

Відповісти
Підтримати
anonymous 27.10.2009 11:28

plochish, плз, убей себя об стену, песдатое чмо.

Відповісти
Підтримати
anonymous 27.10.2009 02:50

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

ебаный в рот

[звонко ударяется башкой о палубу]

Відповісти
Підтримати
anonymous 27.10.2009 02:43

to hellip

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

ууу скока комплексов сразу вылезло:)

Однако бесспорным является и то, что по статистике, у таких, как я, есть хорошие шансы сохраниться в строю айтишнегов к тому моменту, когда подавляющее большинство сегодняшних олдфагов, активно п****щих остальное «быдло», уже будет нетранспортабельно.

Сынок пойди подрочи

Відповісти
Підтримати
anonymous 26.10.2009 23:16
Как то неожиданно вселенные опять появились...

Хорошо. Тогда давай будем считать, что в самой первой фразе вместо N вселенных — N состояний квантового компьютера, на котором вычисляются среди прочего значения рекурсивной функции f (i), i = 1,..., N.

Квантовая версия чего?

Программы оценки курса. Классическая программа исполняется на классической машине Тьюринга, квантовая — на универсальном компьютере, допускающем квантовую суперпозицию элементов для моделирования любой другой машины Тьюринга.

Это стратегия? Что обозначает результат?

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

Почему в среднем это так?
Состояние квантового компьютера, выполняющего программу оценки курса f (i), будет таково:
1/sqrt (2) * (|0, f (0) > +|1, f (1) >).
Измерение любого невырожденного наблюдаемого состояния даст один из четырех возможных результатов: |0> = (½) (|0, 0> —|0, 1> +|1, 0> —|1, 1>), |1> = (½) (|0, 0> —|0, 1> —|1, 0> +|1, 1>), |FAIL> = (½) (|0, 0> +|0, 1> +|1, 0> +|1, 1>), |ERROR> = (½) (|0, 0> +|0, 1> —|1, 0> —|1, 1>).

Эти четыре состояния образуют ортонормированное векторное множество. Следовательно, результирующее наблюдаемое состояние достоверно существует при любом способе измерений. Если измерение дало значение с амплитудой 0 или 1, то автоматически и функция стратегии G (f) == f (0) + f (1) или, лучше, G (f) == f (0) XOR f (1) даст значение 0 или 1. Условно можно принять, что если 0 — мы играем на повышение, если 1 — играем на понижение. Как бы там ни было, этот продуктивный результат, дающий возможность построить осмысленную стратегию на основании сведений о значении функции G (f), появляется с вероятностью ½. Вне зависимости от природы функции f с той же вероятностью ½ в одном из квантовых регистров появляется состояние|FAIL>. В этом случае инвестиции делать не следует, поскольку о значении функции стратегии нельзя сделать определенного вывода. Если в том регистре, состояние которого мы проверили, появилось состояние|FAIL>, мы не только знаем, что сегодня инвестиции делать не следует, но и избавлены от необходимости проверять второй регистр, поскольку состояния двух регистров взаимно перепутаны, и из информации о состоянии одного можно почерпнуть информацию о состоянии другого. В предположении, разумеется, что вероятность состояния|ERROR> можно сделать достаточно малой для практических нужд. Для N = 2 это тривиальный результат, но при большем количестве квантовых элементов он имеет те самые последствия в виде предельной эффективности, что я озвучил выше.

От меня ускользнул механизм объединения.
Имеется в виду, что результат такой, как если бы он вычислялся на классической машине Тьюринга в течение двух процессоро-дней.

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

И что это нам дает если мы в «неправильной вселенной»?

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

Відповісти
Підтримати
crypto5 26.10.2009 21:43

Если чесно, твои рассуждения может и имеют рациональное зерно, но выглядят очень не связанно.

В простейшем варианте стратегия реализуется для двух вселенных

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

G (f) == f (0) + f (1)

Это стратегия? Что обозначает результат?

Если квантовая версия

Квантовая версия чего?

то в среднем в один день из двух ячеек в одной будет значение «1», соответствующее неудаче (или наоборот, это не принципиально).

Почему в среднем это так?

Итак, функция G (f), объединяющая результаты двух классических дней, вычисляется квантовым процессором за один день.

От меня ускользнул механизм объединения.

В этом смысле более общее утверждение говорит, что если подзадачи N-кратной распараллеленной задачи распределяются между (N^2 — 2*N + 2) вселенными, то по крайней мере в одной из них может быть получен окончательный результат.

И что это нам дает если мы в «неправильной вселенной»?

Відповісти
Підтримати
anonymous 26.10.2009 20:49
Звучит как, а давайте будем считать что при подбрасывании монетки у нас будет две паралельные вселенные, с разными вариантами подбрасывания.

Вот, вы все правильно понимаете. Именно так и обстоит дело в эвереттике.

Какой практический смысл этого «и так часто и поступают».
Практический смысл выявляется при переходе к квантовым компьютерам. Пусть у вас есть стратегия инвестиций на фондовой бирже G (f) и программа статистической оценки изменений курса на завтра по сегодняшнему его состоянию. В простейшем варианте стратегия реализуется для двух вселенных, G (f) == f (0) + f (1), здесь f — рекурсивная функция, определяющая поведение квантовой обратимой машины Тьюринга для двух кубитов — (0) и (1). Если квантовая версия работает каждый день, то в среднем в один день из двух ячеек в одной будет значение «1», соответствующее неудаче (или наоборот, это не принципиально). Но с той же средней частотой появляется и «0» — индикатор корректного значения стратегической функции в другой зацепленной ячейке. Итак, функция G (f), объединяющая результаты двух классических дней, вычисляется квантовым процессором за один день. Вопрос: где вычислен ответ для дополнительного дня?

В этом смысле более общее утверждение говорит, что если подзадачи N-кратной распараллеленной задачи распределяются между (N^2 — 2*N + 2) вселенными, то по крайней мере в одной из них может быть получен окончательный результат.

Відповісти
Підтримати
crypto5 26.10.2009 20:34

С физической точки зрения (эвереттика) ничто не мешает считать, что каждый вектор относится к одной из параллельных вселенных, и так часто и поступают.

Смешно. Звучит как, а давайте будем считать что при подбрасывании монетки у нас будет две паралельные вселенные, с разными вариантами подбрасывания. Конечно такое можно нафантазировать, но какое это имеет отношение к математике? Какой практический смысл этого «и так часто и поступают».

Відповісти
Підтримати
anonymous 26.10.2009 20:14
Из вероятностной логики Нильсена.

Пример. Пусть есть логические формулы: А, В, А \supset B. Возможны четыре вектора, указывающие на разные интерпретации этих высказываний в терминах истины и лжи. С физической точки зрения (эвереттика) ничто не мешает считать, что каждый вектор относится к одной из параллельных вселенных, и так часто и поступают.

... вокруг отрасли крутится...

Да, вы правы. Не вокруг, а в отрасли. Ну так тем хуже.
PS. Вообще, подводя итог нашему с motus маленькому флеймику, хочу заметить, что спор с таким закаленным олдфагом, как Сергей, бесспорно, относится к числу наиболее престижных и трудных дисциплин Специальной Олимпиады. Ситуация усугубляется тем, что у некоторых специалистов, выехавших из xUSSR в Пиндосию, возникает непреодолимое желание в свободное от работы время извергнуть с высокой колокольни поток отходов на каждого, кто имел несчастье родиться позже и/или не разделяет мотивов, побудивших упомянутого специалиста податься за океан. (Это, например, не относится к уважаемым junior_dev и crypto5 .) В процессе вброса отходов на вентилятор эмигрант не гнушается самых что ни на есть отмороженных приёмов, надеясь задавить оппонента авторитетом/зарплатой/экспириенсом или на худой конец затроллить его. Интересно, что коренные пиндосские программеры, если судить по дискуссиям в этих ваших интернетах, менее склонны к такому ведению диалога. Глядя в профиль ув. motus’а на линкедине, мне, бедолашному hellip, очевидно, нужно испытать глубочайшее потрясение при виде списка освоенных технологий/законченных университетов/оставленных позади компаний, а также срочно засесть за книжки и блоги в надежде когда-нибудь проапгрейдиться до такого же левела и "свалить из этой страны«© на Заокраинный Запад© *YAHOO* *ROFL*. Но не зря говорят, что наиболее рьяными адептами какой-либо иерархической структуры являются те, кто в ней состоит относительно недавно и активно крутит карусель... Так же и в данном случае. Однако бесспорным является и то, что по статистике, у таких, как я, есть хорошие шансы сохраниться в строю айтишнегов к тому моменту, когда подавляющее большинство сегодняшних олдфагов, активно п****щих остальное «быдло», уже будет нетранспортабельно.
Просто в силу возраста, хе-хе.

*YAHOO*

Відповісти
Підтримати
crypto5 26.10.2009 19:02

сосуществующих вселенных

У меня случился когнитивный диссонанс... Это из какой области науки?...

Відповісти
Підтримати
anonymous 26.10.2009 17:48

Ггг, motus «вокруг отрасли крутится». Смешно:)

Ну так *YAHOO*; t/

Відповісти
Підтримати
anonymous 26.10.2009 17:25
OK, motus, ты бохъ. Слифф зощитан. Можешь и дальше брызгать тут слюной в одиночестве и упиваться триумфом. На каждый твой пост я в состоянии привести столько ссылок, сколько посчитаю нужным, но тебе ведь не это важно, а возможность *CENSORED*ного огораживания. Ога?

Сколько ушибленных вокруг отрасли крутится, шо ппц.

Відповісти
Підтримати
Sergiy Matusevych вечный чайник 26.10.2009 17:09

Квадратно-гнездовой метод приведен лишь как пример подхода, приводящего для этой задачи к out of memory, это описано многократно в уютненьком, в частности, relyef.livejournal.com.

еще одна левая ссылка, спасибо.

Уэно-Исидзука как раз по теме, там описывается, как разбивать задачи с ненадежными данными на подзадачи так, чтобы в целом задачу можно было описать иерархически в терминах немонотонной вероятностной логики, где правильное решение рассматривается как extension из вектора сосуществующих вселенных по определенным структурой языка правилами вывода.
очередной словесный понос? ну оокей. сделаем вид, что этот поток слов и вправду имеет смысл. так какую задачу на какие подзадачи ты собираешься разбивать? давай я с карандашом и бумажкой сяду и будем вместе разбивать. описывать, так сказать, иерархически. вот я инженер, хочу написать работающий код. расскажи мне, что и как делать., а я тебе за это по знакомству дам ссылочку на секретную статью с описанием PageRank: -)

PS. All: если кто не знает, Уэно-Исидзука это одна из 10, кажется, древних японских книжек по искусственному интеллекту — как его понимали японцы в 80х годах, в рамках их проекта машин 5-го поколения. у нас книжки вышли году в 89−91, когда в всем мире уже настала AI Winter:) впрочем, судя по цитируемости русского перевода, у нас это до сих пор передний край науки:)

Відповісти
Підтримати
anonymous 26.10.2009 13:16

Ме, ну вы упрямец, однако... Ме — это версия Windows, которой вы пользуетесь? А вам известно, что книги когда-то были не только электронными или сосканенными?... И, между прочим, в те времена и были сформулированы некоторые до сих пор нерешенные задачки.

Відповісти
Підтримати
anonymous 26.10.2009 12:58

2hellip:

Уэно-Исидзука как раз по теме

Специально ради интереса погуглил на эту тему, и вот что нашел:
www.google.com.ua/search hl=uk& client=firefox-a& rls=org.mozilla%3Aen-US%3Aofficial& hs=7t4& q=%D0%A3%D1%8D%D0%BD%D0%BE+%D0%98%D1%81%D0%B8%D0%B4%D0%B7%D1%83%D0%BA%D0%B0+%22%D0%9F%D1%80%D0%B5%D0%B4%D1%81%D1%82%D0%B0%D0%B2%D0%BB%D0%B5%D0%BD%D0%B8%D0%B5+%D0%B8+%D0%B8%D1%81%D0%BF%D0%BE%D0%BB%D1%8C%D0%B7%D0%BE%D0%B2%D0%B0%D0%BD%D0%B8%D0%B5+%D0%BD%D0%B5%D1%87%D1%91%D1%82%D0%BA%D0%B8%D1%85+%D0%B7%D0%BD%D0%B0%D0%BD%D0%B8%D0%B9%22+& btnG=%D0%9F%D0%BE%D1%88%D1%83%D0%BA& meta=& aq=f& oq=

Для добавления в список литературы реферата, курсовой или диплома Исидзука покатит, но вот практической пользы от этой книги для топикстартера — полагаю, ноль.

Відповісти
Підтримати
anonymous 26.10.2009 12:37
motus, успокойся, м-м? Квадратно-гнездовой метод приведен лишь как пример подхода, приводящего для этой задачи к out of memory, это описано многократно в уютненьком, в частности, relyef.livejournal.com. Уэно-Исидзука как раз по теме, там описывается, как разбивать задачи с ненадежными данными на подзадачи так, чтобы в целом задачу можно было описать иерархически в терминах немонотонной вероятностной логики, где правильное решение рассматривается как extension из вектора сосуществующих вселенных по определенным структурой языка правилами вывода. Типа, хватит трендеть не по делу *MRGREEN*, а то я так и оставлю тебя по дефолту с репутацией... гм... почетного старожила форума.

PS. "Человеки бывают двух сортов — юзеры и лузеры. Юзеры пользуются, лузеры ползают. Юзеров мало, лузеров навалом. Лузер ли я позорный или царственный юзер?«© Владислав Сурков, «Околоноля»

Відповісти
Підтримати
junior dev 26.10.2009 07:05
:) в том то и дело, что вместо решения задачи потом пошли размышления на тему о высоком, это наверное то о чем вы говорили в другом посте, что сюда приводят не технические, а социальные причины...
кстати модель спелера, как раз и базируеться на вероятностных событиях и вычислениях наиболее релевантного контекста, к примеру Yahoo на misspelling «tel me» дает «tell me», а на «tel net» — «telnet»:) можно еще постемить на тему alterations к words аля word:) (все тоже Yahoo), но куда приятнее пообщаться о высоком:) чем низкоуровневом;)
зачем человеку для простого приложения реализовывать модель линейного класифаера, коим зачастую есть спелер, лейбелить трейнинг сет, обучать, мерять П/Р итд? куда приятнее наверное поговорить не о чем:)

ПыСы: с 18го поста задача перешла в область поисковых систем, до этого обсуждалось лишь техническая реализация алгоритма, который был предложен в 7 м посте с реализацией словаря

Відповісти
Підтримати
Sergiy Matusevych вечный чайник 26.10.2009 06:50

Уэно, Исидзука «Представление и использование нечётких знаний»

hellip, это у тебя прикол такой — совать людям под нос книжки с умными названиями, но совершенно не по теме? Типа, читать все равно никто не будет, а, глядишь, уважать начнут. Еще и квадратно-гнездовой метод с хешем приплел. Сорри, но я на такие дешевые понты уже не ведусь — или рассказывай подробно и по делу, или оставайся по дефолту с репутацией трепла^W ээ... активного участника форума.
All: господа, а мы все еще отвечаем на исходный вопрос? Человек четко поставил задачу — даны два! русских! слова; нужно вычислить расстояние Дамерау-Левенштейна между ними — возможно, с переменной стоимостью замен (и вставок?). Про словарь там вообще ни слова не было! Я понимаю, что даже при таких условиях можно накопать массу узкоспециальной литературы, но готов спорить, что для 99% прикладных задач простейший алгоритм в 5 строк и будет самым подходящим.

С поиском, кстати, аналогично — допустим, и вправду, на входе есть одно слово, и нужно найти ближайшее к нему в словаре. Если нужно просто прикрутить такую фичу к приложению, моя первая мысль — использовать спелчекер: -)

Відповісти
Підтримати
crypto5 26.10.2009 00:12

А что будет класться в Trie? У меня есть несколько предположений, но хотелось бы уточнить.

Відповісти
Підтримати
junior dev 25.10.2009 23:32

Если вы о словаре, то лучше в Trie и тогда поместиться в памяти, туда же было бы не плохо и индекс поместить, ввиду сегодняшних обьемов памяти типа 20−30 гигов оперативы:) то можно поместить достаточно много (имееться ввиду конечно не офисный комп, а рабочая лошадка)

Відповісти
Підтримати
anonymous 25.10.2009 23:16

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

Відповісти
Підтримати
crypto5 25.10.2009 22:14

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

Очевидно, что эту структуру данных можно хранить на диске.

Відповісти
Підтримати
anonymous 25.10.2009 22:04

товаришь с химическим дипломом сможет вам показать слова в 30 буков и выше...

Ага, точно. Вот, например, навскидку: альфа-гидроксигексафторизомасляная (кислота; 33 буквы+дефис).

мы прийдем либо к out-of-memory либо к time-out

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

Відповісти
Підтримати
junior dev 25.10.2009 21:54
всмысле?

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

Відповісти
Підтримати
crypto5 25.10.2009 21:49
junior_dev

А можешь описать задачу которую ты сейчас решаешь?

Відповісти
Підтримати
junior dev 25.10.2009 21:40
есть для слова «забор» есть 2 разных вариата с одной ошибкой — LD = 1
«забор» = { «запор», «забой» } то при выборе какой из вариантов важнее получаеться релеванс, так как если в запросе есть лекарство то скорее вариант № 1, а если шахтеры то № 2:)
что вы подразумеваете под просто списком документов? слова с LD < = 1?

если нужны ВСЕ слова, то как вы понимаете без перебора или избыточного индекса не обойтись, так как Unicode позволяет для каждой позиции иметь 65535 вариантов ошибок, и букаф в слове тоже может быть много (товаришь с химическим дипломом сможет вам показать слова в 30 буков и выше):) то мы прийдем либо к out-of-memory либо к time-out

Відповісти
Підтримати
crypto5 25.10.2009 21:27

это вопрос стоит достаточно дорого:) к примеру Гугль при меньшем индексе чем Яху, имеет лучше релеванс
тут есть 2 момента, что вы хотите расчитать заранее и сложить в индекс, и второе что будет расчитываться на лету и работать с индексом...
к примеру компилятор вначале нормализирует документ, потом уже начинает строить семантическое дерево, и в нем он работает с нормальными формами... и к примеру имя функции не уникально, но он же подбирает лучшую альтернативу и за достаточно вменяемое время:) там тоже не четкий поиск, так как не всегда типы идентичны параметрам вызова
Ух как вас понесло; -)

Начнем с простого, найти просто список документов без учета релевантности!

Відповісти
Підтримати
vitaly_4uk 25.10.2009 20:16

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

Відповісти
Підтримати
junior dev 25.10.2009 20:11

PageRank это не работа с индексом, это критиерий ранжирования документов в нем

Відповісти
Підтримати
anonymous 25.10.2009 20:09

Вот именно. PageRank-то, кажись, охраняют, как Кащей Бессмертный своё яйцо: -))

Відповісти
Підтримати
junior dev 25.10.2009 20:08
это вопрос стоит достаточно дорого:) к примеру Гугль при меньшем индексе чем Яху, имеет лучше релеванс
тут есть 2 момента, что вы хотите расчитать заранее и сложить в индекс, и второе что будет расчитываться на лету и работать с индексом...

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

Відповісти
Підтримати
crypto5 25.10.2009 20:01

можно пойти путем которым идут поисковые машины, индексация слов и поиск через индекс

В том то и вопрос как построить эфективный индекс.

Відповісти
Підтримати
junior dev 25.10.2009 19:59
для уменьшения памяти словаря можно использовать Trie

можно пойти путем которым идут поисковые машины, индексация слов и поиск через индекс

Відповісти
Підтримати
junior dev 25.10.2009 19:59
для уменьшения памяти словаря можно использовать Trie

можно пойти путем которым идут поисковые машины, индексация слов и поиск через индекс

Відповісти
Підтримати
Alexandr Gavriluk .Net developer в Aspose 25.10.2009 19:09
>> #
>> hellip 45 мин. назад
>> Если вы собираетесь учитывать перестановки слов, вы не добьётесь ничего, кроме факториального потребления памяти.
Если по умному составить дерево и подставлять указатель на фразу (документ) где встречается это слово также к ссылкам на слово то полученные выборки уже можно смерджить другими алгоритмами.

Выбираем быстрым нечётким поиском все слова с допустимым уровнем ошибок, получая списки укзателей на фразу. Далее ищем id фразы (перебором или умным перебором с учётом ошибки) куда попадают все или большинство введенных слов. Метод очень быстрый, из недостатков (если задать большой уровень ошибки) может находить «странные фразы». Чтобы это не было все фразы стоит еще проверять по морфологии. Ну и сортировка по уровню суммарной ошибки фразу.

Відповісти
Підтримати
anonymous 25.10.2009 18:07

Если вы собираетесь учитывать перестановки слов, вы не добьётесь ничего, кроме факториального потребления памяти.

Відповісти
Підтримати
Alexandr Gavriluk .Net developer в Aspose 25.10.2009 17:58
Я делал через рекурсивный поиск по дереву словаря, куда уложены все слова, с альфа-отсечениями. Листья дерева предварительно отсортированы по алфавиту, что позволяет использовать бинарный поиск.
Скорость поиска 5−10 мс на Athlon5600+ на одном ядре (использовалось только одно ядро), реализация на Delphi. Недостаток в памяти в виде дерева нужно держать весь словарь. При наличии близких слов, например [дере] во [дере] вья словарь сильно сжимается.

Однако можно и оптимизировать используя мелкую БД типа SQLite с динамической подкачкой словаря — это увеличит время поиска в 2−3 раза (что при его скорости не так уж много), но уменьшит занимаемую память словарём.

Відповісти
Підтримати
crypto5 25.10.2009 17:57

Если задача

Иными словами, на входе имеем два слова, на выходе — расстояние между ними с учетом вышеперечисленного.

то действительно наверное стоит модифицировать алгоритм вычисления расстояния Левенштейна.

Если задача

реализовать нечеткий поиск слов русского языка

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

Відповісти
Підтримати
Bogdan Shyiak SE or Dev 25.10.2009 17:42

Может помогут 10 лекций проф. Шлезингера

А разве Шлезингер занимается анализом текстов, вроде бы он специализируется на распознавании образов.

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

Простите, это вы загнули. Такие вещи хорошо бы знать каждому, кто называет себя программистом.
Я учил по:
Круглов Ли Голунов — Нечеткая логика и искусственные нейронные сети

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

Відповісти
Підтримати
vitaly_4uk 25.10.2009 15:12

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

Відповісти
Підтримати
anonymous 25.10.2009 13:32

Уэно, Исидзука «Представление и использование нечётких знаний»

Відповісти
Підтримати
Andrii Rodionov JUG UA, Викладач в НТУУ «КПІ» та УКУ 25.10.2009 13:18

Может помогут 10 лекций проф. Шлезингера www.irtc.org.ua/...chles/esh10.pdf

Відповісти
Підтримати

Підписатись на коментарі

Не підписуватись