информационная безопасность
без паники и всерьез
 подробно о проектеRambler's Top100
Spanning Tree Protocol: недокументированное применениеАтака на Internet
BugTraq.Ru
Русский BugTraq
 Анализ криптографических сетевых... 
 Модель надежности двухузлового... 
 Специальные марковские модели надежности... 
 Очередное исследование 19 миллиардов... 
 Оптимизация ввода-вывода как инструмент... 
 Зловреды выбирают Lisp и Delphi 
главная обзор RSN блог библиотека закон бред форум dnet о проекте
bugtraq.ru / форум / programming
Имя Пароль
если вы видите этот текст, отключите в настройках форума использование JavaScript
ФОРУМ
все доски
FAQ
IRC
новые сообщения
site updates
guestbook
beginners
sysadmin
programming
operating systems
theory
web building
software
hardware
networking
law
hacking
gadgets
job
dnet
humor
miscellaneous
scrap
регистрация





Легенда:
  новое сообщение
  закрытая нитка
  новое сообщение
  в закрытой нитке
  старое сообщение
[Perl] Попробую рассказать алгоритм поиска в простом варианте 14.04.06 18:22  Число просмотров: 2738
Автор: CheRt Статус: Незарегистрированный пользователь
<"чистая" ссылка>
Вопрос конечно уже уехавший, но вдруг кому понадобится :)

В простейшем варианте поисковик с поддержкой руского языка строится следующим образом.
Принимаем строку, выкидываем все лишнии символы(часто оставляют только a-z а-я - _ + = .)+транслитерация А-Я/а-я, а также всевозможные предлоги(можно по длине слова, хотя грамотнее набор составить).
Сегментируем запрос на блоки(слова).

по циклу
Достаем кусок текста(1 документ), обрабатываем его "на лету", сравниваем(\Q в начале регекспа, если применяем символы из специальных), если находим нужные слова, то записываем их количество(кол-во_найденных==кол-во_сегментов_запроса - полноценный результат, >0, но меньше кол-во_сегментов_запроса - неполноценный)
Записываем, если успешный.
<programming>
[Perl] Безопасный/корректный поисковый запрос по текстовикам 19.03.06 18:02  
Автор: n0xi0uzz <Черкасов Виктор> Статус: Member
<"чистая" ссылка>
Пишу поиск по сайту, где данные хранятся в пресловутых текстовиках. Поиск основан, естественно, на регулярных выражениях. Так вот, когда пытаешься найти символ '[', в error.log пишется: "[Sun Mar 19 17:54:06 2006] [error] [client 127.0.0.1] Unmatched [ in regex; marked by <-- HERE in m/"[ <-- HERE "/ at modules/search.pl line 70.\n". Поэтому, я думаю, этот символ надо "обрезать", т.к. он приводит к ненормальной работе движка.

Я хотел у вас спросить, какие символы ещё стоит "обрезать", как обезопасить свой поиск и сделать, чтобы он не нарушал работу портала?
Ухх... 19.03.06 21:48  
Автор: Heller <Heller> Статус: Elderman
<"чистая" ссылка>
> Пишу поиск по сайту, где данные хранятся в пресловутых
> текстовиках. Поиск основан, естественно, на регулярных
Нагрузка при этом огромна однако.

> выражениях. Так вот, когда пытаешься найти символ '[', в
> error.log пишется: "[Sun Mar 19 17:54:06 2006] [error]
> [client 127.0.0.1] Unmatched [ in regex; marked by <--
> HERE in m/"[ <-- HERE "/ at modules/search.pl line
> 70.\n". Поэтому, я думаю, этот символ надо "обрезать", т.к.
> он приводит к ненормальной работе движка.

>
> Я хотел у вас спросить, какие символы ещё стоит "обрезать",
> как обезопасить свой поиск и сделать, чтобы он не нарушал
> работу портала?
ИМХО вопрос поставлен несовсем корректно. Я бы на твоем месте думал не о том "что обрезать", а о том, "что разрешить". Проверка должна быть такой:
if ($search_line!~/^[\w\d\s]+$/) {fuck_off()}
Если пишешь какой-нибудь синтаксический анализатор, добавь в этот класс необходимые символы (запятые, точки и т. д.).

А вообще делать такой поиск по текстовикам - крайне неразумная вещь. Значительно падает и эффективность и функциональность. Применение хоть какого-то индексирования обязательно, а лучше не "какого-то" а деревья. В крайнем случае готовых поисковых движков в сети с избытком валяется (хотя можно воспользоваться уже готовым сервисом типа Google, который отлично встраивается в любой сайт; слышал так же, что специальный движок предлагает Яндекс, но подробностей не знаю).
Re: 19.03.06 21:58  
Автор: n0xi0uzz <Черкасов Виктор> Статус: Member
<"чистая" ссылка>
Ну, тогда запрещать надо, как я понимаю всё, кроме пробелов и слов состоящих из цифр/букв.

Насчёт деревьев, -- давно ведем с тобой эту дискуссию, ты не мог бы примерный код именно на Perl привести индексирования? Почему-то сишный пример, который ты мне давал и универские конспекты по этому поводу не помогают мне реализовать все это на Perl. Наверное, я тупой %).
В зависимости от задач - нужны разные деревья [update] 17.04.06 12:58  
Автор: amirul <Serge> Статус: The Elderman
Отредактировано 17.04.06 13:05  Количество правок: 1
<"чистая" ссылка>
> Насчёт деревьев, -- давно ведем с тобой эту дискуссию, ты
> не мог бы примерный код именно на Perl привести
> индексирования? Почему-то сишный пример, который ты мне

Если предполагается держать индекс в памяти, то самой дорогой операцией будет сравнение ключей и именно количество сравнений надо минимизировать. Для этого конечно отлично подойдут перловые хеши (если памяти много - минимум раза в три больше, чем нужно для хранения индексов), а если хочется деревьев, то насколько я знаю, самыми эффективными на данный момент являются RB-деревья (red-black trees). Самобалансирующиеся деревья бинарного поиска, гарантирующие логарифмическое время вставки/удаления/поиска для худшего случая.

http://en.wikipedia.org/wiki/Red_black_tree
Вот например его реализация
http://search.cpan.org/~bholzman/Tree-RedBlack-0.3/

Если же индекс предполагается хранить на диске (например он будет слишком большой), то самая дорогая операция - обмен с диском (чтение/запись кластера) и минимизировать надо количество обращений к диску. Здесь практически без вариантов B-Tree (дисковый хеш бывает, но рехеш - изменение размера хеша - ОЧЕНЬ дорогая операция, поэтому стоит его применять либо для статичных данных, либо сразу резервировать хеш-таблицу с огромным запасом). B-Tree тоже гарантирует логарифмическое количество обращений к диску для худшего случая для всех основных "древесных" операций.

http://en.wikipedia.org/wiki/B-tree
http://perl.plover.com/BTree/

> давал и универские конспекты по этому поводу не помогают
> мне реализовать все это на Perl. Наверное, я тупой %).

Хотя если ты действительно хочешь сделать эффективный поиск, то я бы предпочел делать его на C, а перлу отдать биндинги. Насколько я помню стандартная перловская библиотека нормально биндится с Berkeley DB, а большего и не надо - это просто реализация нескольких структур данных (в том числе и B-Tree и Hash) для эффективного хранения и поиска

http://www.sleepycat.com/products/bdb.html
-------------------

Написал кучу всего, а так и не сказал, чего ж использовать в качестве ключа и чего в качестве ассоциированного значения. Для поиска, ключ - слово в верхнем регистре и по возможности без окончаний/суффиксов, а значение - id-шники постов, в которых это слово встречается. Если ты прикрутишь BDB, то ничто не помешает тебе перетащить и сами посты в базу, а не юзать файлы.
[Perl] Попробую рассказать алгоритм поиска в простом варианте 14.04.06 18:22  
Автор: CheRt Статус: Незарегистрированный пользователь
<"чистая" ссылка>
Вопрос конечно уже уехавший, но вдруг кому понадобится :)

В простейшем варианте поисковик с поддержкой руского языка строится следующим образом.
Принимаем строку, выкидываем все лишнии символы(часто оставляют только a-z а-я - _ + = .)+транслитерация А-Я/а-я, а также всевозможные предлоги(можно по длине слова, хотя грамотнее набор составить).
Сегментируем запрос на блоки(слова).

по циклу
Достаем кусок текста(1 документ), обрабатываем его "на лету", сравниваем(\Q в начале регекспа, если применяем символы из специальных), если находим нужные слова, то записываем их количество(кол-во_найденных==кол-во_сегментов_запроса - полноценный результат, >0, но меньше кол-во_сегментов_запроса - неполноценный)
Записываем, если успешный.
1




Rambler's Top100
Рейтинг@Mail.ru


  Copyright © 2001-2025 Dmitry Leonov   Page build time: 0 s   Design: Vadim Derkach