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

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

Вернуться   Форум программистов > IT форум > Общие вопросы по программированию, компьютерный форум
Регистрация

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

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

Ответ
 
Опции темы Поиск в этой теме
Старый 29.08.2012, 21:28   #1
Stilet
Белик Виталий :)
Старожил
 
Аватар для Stilet
 
Регистрация: 23.07.2007
Сообщений: 57,792
По умолчанию Полнотекстовый поиск с нестрогим совпадением

Всем доброго. Появилась задача быстрого поиска в неком списке.
Список этот представляет собой строки слов, которые ищутся, отсортированный по возрастанию:
Цитата:
123
456
789
Все хорошо если я ищу полностью слово, например 456.
Но предположим привередливый клиент не знает как слово начинается (кстати по ТЗ слова фиксированной длины и всегда содержат 10 символов - не более не менее), а знает только часть слова.
Допустим в данном примере я задаю критерий поиска - "56", и ожидаю результат - "456".
Как поступать в таких случаях? Полный проход не устраивает, зачем тогда индексация списка. Есть ли алгоритмы поиска с нестрогим совпадением в отсортированном списке?
I'm learning to live...
Stilet вне форума Ответить с цитированием
Старый 30.08.2012, 13:28   #2
Аватар
Старожил
 
Аватар для Аватар
 
Регистрация: 17.11.2010
Сообщений: 19,042
По умолчанию

1. Засунуть в базу и like (шутка, а может и серьезно)

2. Допустим минимальная длина вводимого слова 7. Держать 4 индекса и поиск по каждому из них. Захочется ли индексы строить?

Индекс 1 - по 10 символам
Индекс 2 - по 9 символам начиная со 2-го
Индекс 3 - по 8 символам начиная со 3-го
Индекс 4 - по 7 символам начиная со 4-го
Если бы архитекторы строили здания так, как программисты пишут программы, то первый залетевший дятел разрушил бы цивилизацию
Аватар вне форума Ответить с цитированием
Старый 30.08.2012, 15:09   #3
Stilet
Белик Виталий :)
Старожил
 
Аватар для Stilet
 
Регистрация: 23.07.2007
Сообщений: 57,792
По умолчанию

Цитата:
Засунуть в базу и like
Предполагается самописная БД, не знающая о существовании SQL
Цитата:
Держать 4 индекса и поиск по каждому из них.
Ну не знаю... Стремноватая идейка.
I'm learning to live...
Stilet вне форума Ответить с цитированием
Старый 30.08.2012, 15:28   #4
waleri
Старожил
 
Регистрация: 13.07.2012
Сообщений: 6,493
По умолчанию

Делать индекс начиная с каждой буквы слова, т.е. так же как сказал "Аватар" но в одном индексе.
waleri вне форума Ответить с цитированием
Старый 30.08.2012, 16:14   #5
Stilet
Белик Виталий :)
Старожил
 
Аватар для Stilet
 
Регистрация: 23.07.2007
Сообщений: 57,792
По умолчанию

Цитата:
Делать индекс начиная с каждой буквы слова
Тоесть?
И сколько этих индексов будет?
I'm learning to live...
Stilet вне форума Ответить с цитированием
Старый 30.08.2012, 17:45   #6
evg_m
Старожил
 
Регистрация: 20.04.2008
Сообщений: 5,515
По умолчанию

алфавит-то большой? цифры, буквы, все что придется?

мысль первая
построить индексы вхождения символов
1 - отсортированный список индексов строк содержащих 1
2 - то же для 2
и т.д.

поиск по части = пересечение нескольких отсортированных списков.

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

мысль вторая
заменить списки символов на списки биграмм. (по сути мы просто увеличиваем алфавит)

мысль третья
списки символов с указанием позиции в строке и сортировкой по позиции + индекс строки.
усложняется процесс построения пересечения списков.
программа — запись алгоритма на языке понятном транслятору
evg_m вне форума Ответить с цитированием
Старый 01.09.2012, 17:41   #7
still_alive
Great Code Monkey
Форумчанин
 
Аватар для still_alive
 
Регистрация: 09.08.2007
Сообщений: 533
По умолчанию

Нужно построить суффиксное дерево по базе образцов и искать в нем.
still_alive вне форума Ответить с цитированием
Старый 01.09.2012, 18:56   #8
Stilet
Белик Виталий :)
Старожил
 
Аватар для Stilet
 
Регистрация: 23.07.2007
Сообщений: 57,792
По умолчанию

Цитата:
still_alive
Намек понял, почитаю.
I'm learning to live...
Stilet вне форума Ответить с цитированием
Старый 15.09.2012, 17:46   #9
Rififi
Старожил
 
Регистрация: 19.08.2009
Сообщений: 2,120
По умолчанию

Stilet

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

Apache Lucene
Rififi вне форума Ответить с цитированием
Старый 15.09.2012, 19:56   #10
Stilet
Белик Виталий :)
Старожил
 
Аватар для Stilet
 
Регистрация: 23.07.2007
Сообщений: 57,792
По умолчанию

Хм... Стороннего ничего не хочется брать.
Да и потом я пожалуй пересмотрю стратегию. Где-то что-то я в условии задачи упустил узкоспециализированного... По крайней мере у меня такое чувство.
I'm learning to live...
Stilet вне форума Ответить с цитированием
Ответ


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

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

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


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Полнотекстовый поиск MySQL gunsoy SQL, базы данных 3 19.08.2012 17:45
fulltext mysql Полнотекстовый поиск gunsoy SQL, базы данных 2 23.10.2011 17:15
Поиск по БД jaxik БД в Delphi 8 08.09.2010 03:41
Поиск в бд KAKTYC SQL, базы данных 3 25.07.2008 13:21
ПОИСК В БД HOMER БД в Delphi 2 20.12.2007 21:41