![]() |
|
|
Регистрация Восстановить пароль |
Повторная активизация e-mail |
Регистрация | Задать вопрос |
Заплачу за решение |
Новые сообщения |
Сообщения за день |
Расширенный поиск |
Правила |
Всё прочитано |
![]() |
|
Опции темы | Поиск в этой теме |
![]() |
#1 | |
Белик Виталий :)
Старожил
Регистрация: 23.07.2007
Сообщений: 57,097
|
![]()
Всем доброго. Появилась задача быстрого поиска в неком списке.
Список этот представляет собой строки слов, которые ищутся, отсортированный по возрастанию: Цитата:
Но предположим привередливый клиент не знает как слово начинается (кстати по ТЗ слова фиксированной длины и всегда содержат 10 символов - не более не менее), а знает только часть слова. Допустим в данном примере я задаю критерий поиска - "56", и ожидаю результат - "456". Как поступать в таких случаях? Полный проход не устраивает, зачем тогда индексация списка. Есть ли алгоритмы поиска с нестрогим совпадением в отсортированном списке?
I'm learning to live...
|
|
![]() |
![]() |
![]() |
#2 |
Старожил
Регистрация: 17.11.2010
Сообщений: 18,922
|
![]()
1. Засунуть в базу и like (шутка, а может и серьезно
![]() 2. Допустим минимальная длина вводимого слова 7. Держать 4 индекса и поиск по каждому из них. Захочется ли индексы строить? Индекс 1 - по 10 символам Индекс 2 - по 9 символам начиная со 2-го Индекс 3 - по 8 символам начиная со 3-го Индекс 4 - по 7 символам начиная со 4-го
Если бы архитекторы строили здания так, как программисты пишут программы, то первый залетевший дятел разрушил бы цивилизацию
|
![]() |
![]() |
![]() |
#3 | ||
Белик Виталий :)
Старожил
Регистрация: 23.07.2007
Сообщений: 57,097
|
![]() Цитата:
![]() Цитата:
I'm learning to live...
|
||
![]() |
![]() |
![]() |
#4 |
Старожил
Регистрация: 13.07.2012
Сообщений: 6,331
|
![]()
Делать индекс начиная с каждой буквы слова, т.е. так же как сказал "Аватар" но в одном индексе.
|
![]() |
![]() |
![]() |
#5 | |
Белик Виталий :)
Старожил
Регистрация: 23.07.2007
Сообщений: 57,097
|
![]() Цитата:
И сколько этих индексов будет?
I'm learning to live...
|
|
![]() |
![]() |
![]() |
#6 | |
Старожил
Регистрация: 20.04.2008
Сообщений: 5,527
|
![]()
алфавит-то большой? цифры, буквы, все что придется?
мысль первая построить индексы вхождения символов 1 - отсортированный список индексов строк содержащих 1 2 - то же для 2 и т.д. поиск по части = пересечение нескольких отсортированных списков. Цитата:
если алфавит большой можно попробовать. мысль вторая заменить списки символов на списки биграмм. (по сути мы просто увеличиваем алфавит) мысль третья списки символов с указанием позиции в строке и сортировкой по позиции + индекс строки. усложняется процесс построения пересечения списков.
программа — запись алгоритма на языке понятном транслятору
|
|
![]() |
![]() |
![]() |
#7 |
Great Code Monkey
Форумчанин
Регистрация: 09.08.2007
Сообщений: 533
|
![]()
Нужно построить суффиксное дерево по базе образцов и искать в нем.
|
![]() |
![]() |
![]() |
#8 | |
Белик Виталий :)
Старожил
Регистрация: 23.07.2007
Сообщений: 57,097
|
![]() Цитата:
I'm learning to live...
|
|
![]() |
![]() |
![]() |
#9 |
Старожил
Регистрация: 19.08.2009
Сообщений: 2,119
|
![]()
А вы почему со мной не соглашаетесь, у вас что, импотенция? (c) ACE Valery
|
![]() |
![]() |
![]() |
#10 |
Белик Виталий :)
Старожил
Регистрация: 23.07.2007
Сообщений: 57,097
|
![]()
Хм... Стороннего ничего не хочется брать.
Да и потом я пожалуй пересмотрю стратегию. Где-то что-то я в условии задачи упустил узкоспециализированного... По крайней мере у меня такое чувство.
I'm learning to live...
|
![]() |
![]() |
![]() |
![]() |
||||
Тема | Автор | Раздел | Ответов | Последнее сообщение |
Полнотекстовый поиск 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 |