|
|
Регистрация Восстановить пароль |
Повторная активизация e-mail |
Регистрация | Задать вопрос |
Заплачу за решение |
Новые сообщения |
Сообщения за день |
Расширенный поиск |
Правила |
Всё прочитано |
|
Опции темы | Поиск в этой теме |
29.08.2012, 21:28 | #1 | |
Белик Виталий :)
Старожил
Регистрация: 23.07.2007
Сообщений: 57,792
|
Полнотекстовый поиск с нестрогим совпадением
Всем доброго. Появилась задача быстрого поиска в неком списке.
Список этот представляет собой строки слов, которые ищутся, отсортированный по возрастанию: Цитата:
Но предположим привередливый клиент не знает как слово начинается (кстати по ТЗ слова фиксированной длины и всегда содержат 10 символов - не более не менее), а знает только часть слова. Допустим в данном примере я задаю критерий поиска - "56", и ожидаю результат - "456". Как поступать в таких случаях? Полный проход не устраивает, зачем тогда индексация списка. Есть ли алгоритмы поиска с нестрогим совпадением в отсортированном списке?
I'm learning to live...
|
|
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 | ||
Белик Виталий :)
Старожил
Регистрация: 23.07.2007
Сообщений: 57,792
|
Цитата:
Цитата:
I'm learning to live...
|
||
30.08.2012, 15:28 | #4 |
Старожил
Регистрация: 13.07.2012
Сообщений: 6,493
|
Делать индекс начиная с каждой буквы слова, т.е. так же как сказал "Аватар" но в одном индексе.
|
30.08.2012, 16:14 | #5 | |
Белик Виталий :)
Старожил
Регистрация: 23.07.2007
Сообщений: 57,792
|
Цитата:
И сколько этих индексов будет?
I'm learning to live...
|
|
30.08.2012, 17:45 | #6 | |
Старожил
Регистрация: 20.04.2008
Сообщений: 5,515
|
алфавит-то большой? цифры, буквы, все что придется?
мысль первая построить индексы вхождения символов 1 - отсортированный список индексов строк содержащих 1 2 - то же для 2 и т.д. поиск по части = пересечение нескольких отсортированных списков. Цитата:
если алфавит большой можно попробовать. мысль вторая заменить списки символов на списки биграмм. (по сути мы просто увеличиваем алфавит) мысль третья списки символов с указанием позиции в строке и сортировкой по позиции + индекс строки. усложняется процесс построения пересечения списков.
программа — запись алгоритма на языке понятном транслятору
|
|
01.09.2012, 17:41 | #7 |
Great Code Monkey
Форумчанин
Регистрация: 09.08.2007
Сообщений: 533
|
Нужно построить суффиксное дерево по базе образцов и искать в нем.
|
01.09.2012, 18:56 | #8 | |
Белик Виталий :)
Старожил
Регистрация: 23.07.2007
Сообщений: 57,792
|
Цитата:
I'm learning to live...
|
|
15.09.2012, 17:46 | #9 |
Старожил
Регистрация: 19.08.2009
Сообщений: 2,120
|
А вы почему со мной не соглашаетесь, у вас что, импотенция? (c) ACE Valery
|
15.09.2012, 19:56 | #10 |
Белик Виталий :)
Старожил
Регистрация: 23.07.2007
Сообщений: 57,792
|
Хм... Стороннего ничего не хочется брать.
Да и потом я пожалуй пересмотрю стратегию. Где-то что-то я в условии задачи упустил узкоспециализированного... По крайней мере у меня такое чувство.
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 |