GotAI.NET

Форум: Проблемы искусственного интеллекта

 

Регистрация | Вход

 Все темы | Новая тема Стр.2 (2)<< < Пред.   Поиск:  
 Автор Тема: На: Поиск слова
Плюмаж
Сообщений: 110
На: Поиск слова
Добавлено: 09 авг 07 1:19
Вы знаете, я сейчас протестировал архив, на который ссылка, - пишет "No errors found".

Быть может, какая-то проблема при передаче файла, или что-нибудь на Вашей стороне. Если хотите, то есть два варианта:

1. Попробовать arj-архив http://rundschau.narod.ru/FindWordV1.arj (230 кб)

2. Электронная почта

Вотъ.

Спасибо.
[Ответ][Цитата]
Corwin
Сообщений: 1324
На: Поиск слова
Добавлено: 09 авг 07 1:58
Вот некоторые интернет ресурсы в которых описываеться алгоритмы поиска слов:

Неплохая сборка алгоритмов поиска слов
http://algolist.manual.ru/search/index.php

Алгоритм Ахо-Корасик. Поиск по дереву (бору)
http://aho-corasick.narod.ru/

Статя на Rsdn
http://rsdn.ru/article/alg/textsearch.xml
[Ответ][Цитата]
daner
Сообщений: 4593
На: Поиск слова
Добавлено: 09 авг 07 2:16
Интересный алгоритм Плюмаж. только вы разные вещи делаете.
Вы похожие слова ищите. А Crowin искал точные...
Ваш алг. точные слова долго искать будет. да и на счет памяти... больно много ее уходит.
если текст из N слов, то получается экспоненциальное съедание памяти (все возможные комбинации букв текста), а соответственно и скорости сравнения слова и текста не приемлемы, так как экспоненциальны.

corwin, может все же поделитесь своим алгоритмом? берите пример с Плюмажа. А то просто смотреть на ваши скорости интереса нет.
[Ответ][Цитата]
Corwin
Сообщений: 1324
На: Поиск слова
Добавлено: 09 авг 07 3:07
>Вы похожие слова ищите. А Crowin искал точные...

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

>corwin, может все же поделитесь своим алгоритмом?

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

>А то просто смотреть на ваши скорости интереса нет.

Я написал эти алгоритмы чтобы посмотреть на эффективность теории "быстрого чтения". И скорости соответственно используются именно для этих целей (писать наиболее быстрый и эффективный способ поиска слова не являлось моей целю). Собственно для проверки теории и хотелось увидеть рабочими еще несколько алгоритмов, чтобы было с чем сравнивать.
А вывод получился: человеческий способ быстрого чтения (в моем понимании), всетаки по скорости проигрывает компьютерному поиску по дереву, зато выигрывает по качеству чтения дефектных текстов.
[Ответ][Цитата]
Corwin
Сообщений: 1324
На: Поиск слова
Добавлено: 10 авг 07 1:07
А мне Ваша программа, Плюмаж, понравилась больше чем моя..
Хороший, интуитивно понятный интерфейс у Вас получился. И качество поиска на высоте.

У меня получились следующие замеры скорости:
Слово "человек" - 63 миллисекунд
Слово "информационного" - 218 миллисекунд

Затраты памяти:

Logos.exe (моя)
Без базы 19 Мб
с базой - 24.3 Мб
(Прирост 5.3 Мб)

FindWord_v1.exe (Плюмажа)
без базы - 788 Кб
с базой - 2.8 Мб
(Прирост 785.2 Кб)

Хороший алгоритм Вы предложили
[Ответ][Цитата]
anatoli
Сообщений: 249
На: Поиск слова
Добавлено: 12 авг 07 15:11
Нее.. вывод неправильный.. : )))

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

Во-вторых, что касается поиска по дереву - то это алгоритм другого класса. Он хорошо подходит только для точного поиска. Кстати, не знаю уж как вы его имплементили, но хорошо написанный алгоритм поиска по дереву при поиске слова из 12 символов в базе с 2000 слов не может занять и нескольких МИКРОсекунд (максимальное количество сравнений для 12-ти буквенного слова при полной насыщенности словаря (если он содержит 3 * 10^18 слов) всего 396). Однако эффективно применить его для неточного поиска достаточно сложно.

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

Посему, видится мне, в этот раз Плюмаж глаголет истину - алгоритмы просто по скорости сравнивать не совсем корректно. Сначала их нужно отнести к какой-либо группе алгоритмов (точный поиск - небольшое слово - большая база, точный поиск - большое слово - небольшая база, неточный поиск - небольшое слово - небольшая база и т.п.), а потом уже можно сравнивать. И то, опять-таки, что сравнивать? Скорость? А может быть memory-footprint? Да и то, это только в том случае, если результаты у них абсолютно идентичные. А если результаты заведомо идентичными быть не могут, то более корректно сравнивать точность результатов, а потом уже соотношение точность/скорость.

Ну а в-четвертых, человеку (также как и OCR) без неточного алгоритма не обойтись. Иначе бы пришлось четко рассматривать каждую букву и невозможно было бы интерпретировать информацию с ошибками. Но у человека этот алгоритм гораздо более оптимальный/быстрый (в аналитическом плане). Как я уже и говорил, при разработке AI-систем надо смотреть на человека.
[Ответ][Цитата]
daner
Сообщений: 4593
На: Поиск слова
Добавлено: 12 авг 07 17:39
Ну так естественно, что два сравниваемых способа должны решать одну и туже задачу
а то как сравнивать красное и траву?
Как вы правильно заметили, чёткий поиск отлично сравнивается по кол-ву сравнений (и не нужны здесь никакие замеры в секундах), а не чёткий... есть пара способов сравнения из IR, как сравнивают поисковые движки.
Но если говорить о чтении (как человек), то задача понятна - поиск ОДНОГО подходящего слова.
А дальше сравнить скорость, память и точность... Не обязательно выражать все в одной цифре.
[Ответ][Цитата]
Corwin
Сообщений: 1324
На: Поиск слова
Добавлено: 12 авг 07 22:03
>Нее.. вывод неправильный.. : )))

Спасибо за столь конструктивную критику

>тот алгоритм "человеческого способа", что Вы описали, как я уже говорил - далеко не полный.

А я на полность и не расчитывал.. Так мысли вслух и их практическая проверка Кроме того, согласитесь, что внешне алгоритм довольно похож на метод "человеческого способа" быстрого чтения (хотя я и не претендую на его 100% правильность и полность).
К сожалению не увидел Ваших размышлений по поводу эффекта быстрого чтения..

>не знаю уж как вы его имплементили

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

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

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

>Как я уже и говорил, при разработке AI-систем надо смотреть на человека.

Именно это я попытался сделать У Вас есть другие предложения?
[Ответ][Цитата]
anatoli
Сообщений: 249
На: Поиск слова
Добавлено: 14 авг 07 16:47
> Кроме того, согласитесь, что внешне алгоритм довольно похож на метод "человеческого способа" быстрого чтения

Я бы сказал - это такая сильно упрощенная модель..

Мои размышления таковы: дабы описать способ распознавания текста человеком, надо описать еще примерно 10 первичных функциональностей и еще пару десятков вторичных.. + связи между ними.. Поэтому просто счел более простым не писать по этому поводу вообще ничего конкретного. Я сейчас работаю над этими темами (потенциальные способы имплементации системы визуального восприятия для компьютера + ориентация в пространстве) в то "свободное" время, что остается после всех остальных дел.. Так что работа идет не ахти как быстро.. Когда будет все готово, думаю, опубликую пэйпер (если работа будет стоящей), и тогда все смогут прочитать.. А так пока законченного описания нет, есть неточности.. конкретно говорить пока не о чем..


> но по крайней мере оба алгоритма ("интеллектуальный" и дерева) написаны максимально приближенно один к одному

хм.. чего-то я не очень понимаю - а зачем писать дерево на интеллектуальном замесе? Там же очень простая и четкая логика.


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

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


>> Как я уже и говорил, при разработке AI-систем надо смотреть на человека.
> Именно это я попытался сделать У Вас есть другие предложения?

Правильно, это я и говорю.. но надо смотреть еще больше, еще глубже.. еще больше осмысливая..
[Ответ][Цитата]
Corwin
Сообщений: 1324
На: Поиск слова
Добавлено: 14 авг 07 17:31
>Я бы сказал - это такая сильно упрощенная модель..

Сложно об этом судить... Возможно Вы правы. Лично мое мнение что модель дает неплохие и вполне достаточные (для употребления) результаты.

>Так а тогда пропадет всякий смысл вообще их использования.

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

>но надо смотреть еще больше, еще глубже.. еще больше осмысливая..

У меня когда-то сложилось впечатление что чем глубже залазишь в алгоритмы работы человека, то тем меньше они напоминают человека и больше обычные компьютерные программы Напоминает фразу "Все гениальное - просто"
[Ответ][Цитата]
Corwin
Сообщений: 1324
На: Поиск слова
Добавлено: 23 апр 08 1:30
Нашел интересный алгоритм разработанный еще в 1965 году
Расстояние Левенштейна
Алгоритм позволяет подсчитать количество отличий меду двумя строками.
Испытать алгоритм в работе можно в онлайне:
http://odur.let.rug.nl/~kleiweg/lev/
[Ответ][Цитата]
Corwin
Сообщений: 1324
На: Поиск слова
Добавлено: 25 апр 08 20:55
[Ответ][Цитата]
daner
Сообщений: 4593
На: Поиск слова
Добавлено: 25 апр 08 23:18
Цитата:
Автор: Corwin

Расширяем список ссылок:
Алгоритмы приблизительного сравнения текста

спасибо. хорошая статейка. коротко и ясно.
[Ответ][Цитата]
гость
195.22.126.*
На: Алгоритмы поиска слова
Добавлено: 19 мар 18 17:37
Цитата:
Автор: Corwin

Предлагаю обсудить различные алгоритмы поиска слова (строгие и нестрогие) в базе данных. Такой поиск может быть необходим для нахождения индекса слова в базе данных и соответственно должен проходить достаточно быстро.
Кто то ишет слово, а кто то ДЕЛО, первые философы, вторые - ДЕЯТЕЛИ, бизнесмены, руководители.
[Ответ][Цитата]
 Стр.2 (2)1  [2]<< < Пред.