Быстрый поиск комбинации строк в массиве

← →
Юрий Зотов © (2015-05-23 19:49) [0]

Java.

В памяти лежит массив записей (неотсортированный, но если надо, то можно и отсортировать). Записей в массиве порядка миллиона. Каждая запись содержит 3 раздельные строки (ФИО).

Еще в памяти есть входные ФИО (тоже 3 раздельные строки). Задача - найти в массиве все записи, у которых ФИО совпадают со входными ФИО.

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

Дополнительная информация:
1. Все строки уже в верхнем регистре.
2. Отчество может быть пустым, фамилия и имя всегда заполнены.
3. Букву Ё считаем буквой Е.

Спасибо заранее. Я знаю, что All может все.

← →
Юрий Зотов © (2015-05-23 20:02) [1]

То есть, нужно некое подобие такого запроса:

select ... from ... where
translate(upper(LastName), "Ё", "Е") = :param1 -- фамилия
and -- то же самое для имени и отчества

Собственно, исходная информация из таблицы БД и берется, но медленно ( в таблице есть индекс по ФИО, но translate и upper его убивают). База - DB2.

← →
Kerk © (2015-05-23 20:14) [2]

Чем тут не подходит обычная хэш-таблица?

← →
Jeer © (2015-05-23 20:19) [3]

Юр, что-то непонятна постановка.
1. Запись, это есть и строка.
Сущности Ф.И.О в строке (записи) могут быть разнесены по полям (колонкам) записи.
Ты об этом?

2. При чем тут какая-то "память" и DB2?
Данные лежат в БД? Тогда все остальное - особенности.

← →
Rouse_ © (2015-05-23 20:21) [4]

FTS на данные (а-ля индекс) и всех делоф

← →
Rouse_ © (2015-05-23 20:23) [5]

Юр уйди от баз - у тебя же РО как я понял, там вме в разы проще со скоростью

← →
Rouse_ © (2015-05-23 20:26) [6]

Просто попиариться - выборка данных по введенному слову менее полутора секунд, общий обьем базы за 40 гектаров

← →
Jeer © (2015-05-23 21:19) [7]

Ну да, и поиск/выборка 2 килозаписей приведет к 1.5*2000 = 3000 сек, почти час.

← →
Юрий Зотов © (2015-05-23 21:44) [8]

> Rouse_ © (23.05.15 20:26) [6]

У меня поисковых слов не одно, а комбинация из трех. И таких входных комбинаций 10 тысяч - то есть, поиск среди миллиона записей должен быть повторен 10 тысяч раз. Сейчас я это делаю за 50 минут, а хочется за 10.

← →
Kerk © (2015-05-23 21:51) [9]

> Юрий Зотов © (23.05.15 21:44) [8]

10 тыс обращений к хеш-таблице - это точно быстрее 50 минут.

← →
junglecat © (2015-05-23 21:56) [10]

а если сделать индексируемую вьюху уже с translate & upper?

← →
кгшзх © (2015-05-23 22:10) [11]

Удалено модератором

← →
Pavia © (2015-05-23 22:24) [12]

Тут типичная поисковая задача.

По алгоритмам.
1) Линейный поиск O(N)
2) Бинарный поиск O(Log(N))
3) индексный поиск O(1)

По структурам
1) Массив O(N)
2) Хэш таблица O(1)
3) Дерево O(k*Log(N))

Для ускорения применяют индексирование. Т.е. Создание дополнительной структуры данных для ускорения поиска.

1) Индекс по ключу.
2) Суффиксное дерево
3) Обратный индекс.

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

Для борьбы с Е,Ё во время построения индекса идёт обработка данных - лематизация. Который упрощает слова, до их основы.

Для 1 миллиона вообще сложная артиллерия не нужна. У меня на Delphi линейный поиск отлично отрабатывает за 150-60 мс. И да скорее всего у Вас проблема со скоростью вывода, а не поиска. Так что вам надо проверить. Нет ли лишних накладных расходов. Для Java думаю вам надо будет просто ускорить в 10 раз.
Достаточно проиндексировать по первой букве. Или использовать хэширование по фамилии что тоже будет быстрым. А далее линейным поиском.

← →
D.N. Polezhaev © (2015-05-23 22:50) [13]

Что-то какой то простой вопрос от дяди Юры, потрепаться что ли ))

Давайте выступлю капитаном.

Данная задача в базах данных в чистом виде называется джойном или соединением по русски.

https://ru.m.wikipedia.org/wiki/%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D1%81%D0%BE%D0%B5%D0%B4%D0%B8%D0%BD%D0%B5%D0%BD%D0%B8%D1%8F_(%D0%A1%D0%A3%D0%91%D0%94)

Есть три классических алгоритма соединения.

дядя Юра говорит о том что соединение вложенными циклами работает долго - не удивительно, оно такое.

Остается попробовать соединение хешем или слиянием отсортированных списков. Если сортировать как пишет дядя Юра проблем нету - то последний способ конечно даст самый фантастишь по скорости - параллельно бегаем синхронно по двум отсортированным спискам.

Впрочем при соотношении тысяча к миллиону должен хорошо себя показать и хеш по данным где тысяча, солидарен с Керком.

Можно все это мутить самостоятельно в памяти, но я не понимаю зачем. Уверен, что дб2 в курсе про эти методы соединения и так.

Остается вопрос насчет тормозов функции преобразовния данных. Ну дык и постройте индекс по этой функции, если дб2 умеет строить индексы по функциям. Тогда условие джойна соединения будет

Translate(записьИзБольшойТаблицы) = Translate(записьИзМаленькойТаблицы)

И чтобы Translate был под индексом и там, и там.

Если же по функциям индекс строить не умеет, то денормализация данных и завести колонку с данными для сравнения, где все уже приведено.

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

← →
Pavia © (2015-05-23 22:56) [14]

> У меня поисковых слов не одно, а комбинация из трех. И таких
> входных комбинаций 10 тысяч - то есть, поиск среди миллиона
> записей должен быть повторен 10 тысяч раз. Сейчас я это
> делаю за 50 минут, а хочется за 10.

Берёте БД. Создаёте массив индексов, сортируете его по фамилии с учётом нормировки.
По массиву индексов создадим новый массив фамилий. Делаете нормализацию фамилии. Т.е. приводите к маленьким буквам(к маленьким быстрее так как их больше) заменяете "ё" на "е".
Затем группируете фамилии, указывая порядковый номер начала и конца где фамилии в массиве индексов совпадет.
Это будет массив ключей.

При поиске будете вначале ищете фамилию в массиве ключей. Затем линейный поиск по БД через индексы.

← →
Rouse_ © (2015-05-23 23:02) [15]

При поиисковом запросе в 50 символов на 40 гигах время выборки около 17 секунд (Несколько фраз)
FTS тебе нужен

← →
Pavia © (2015-05-23 23:11) [16]

> При поиисковом запросе в 50 символов на 40 гигах время выборки
> около 17 секунд (Несколько фраз) FTS тебе нужен

Кстати да забыл упомянуть. Прикрутить с СУБД/БД полнотекстовый поиск(FTS). Всяк быстрее чем своё изобретать, делать. Разве что если есть проблемы с памятью и нужно сжать индекс тогда свой вариант лучше.

← →
кгшзх © (2015-05-23 23:11) [17]

добавить индексный массив.
в котором для каждой буквы хранить границы индексов первичного массива.
для всех трех полей.
исходный массив заполнять с сортированного набора данных

я-ву я-ву взял я на ха-ля-вуууу

← →
Inovet © (2015-05-24 04:18) [18]

Ну и я ляпну в довесок. МемориТэйбл какой-нить готовый - с индексами и шахматами, с поэтессами тоже, конечно.

← →
D.N. Polezhaev © (2015-05-24 11:13) [19]

Причем тут вообще полнотекстовый поиск какой то бред пишите. Условия задачи вообще не в этом.

← →
Rouse_ © (2015-05-24 11:17) [20]

Спасибо, мы оценили, особливо за условия задачи. Перечитай чтоли сам вопрос и погугли что есть FTS

← →
Rouse_ © (2015-05-24 11:32) [21]

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

К примеру
ID токена - значение
0 - мама
1 - мыла
2 - раму

документ "мама мыла раму мама мыла раму" содержит блоб токенов вида "012012"

Потом прикрутили движок который ассоциирует пользовательский ввод с токенами и выдает наружу ID документов (буквально 200 миллисекунд на данный тип поиска, ибо уникальных токенов не так много, просадка на выделение памяти под хранение списка ID).

Если требовалось искать точное совпадение - начинал работать второй движок, который работает с массивом токенов, идущих в том порядке, в каком они встречаются в самом документе (тут основная задержка, но на пике выходим на 17 секунд)

← →
Kerk © (2015-05-24 12:05) [22]

> D.N. Polezhaev

Если у человека в руках молоток, то все кажется гвоздем :)

← →
Kerk © (2015-05-24 15:07) [23]

> Rouse_ © (24.05.15 11:32) [21]

Остановись на секунду. У человека три поля, в каждом из них по одному слову максимум. Всего данных - несколько десятков мегабайт максимум. Какие нафиг токены, какой нафиг полнотекстовый поиск, какие нафиг документы? Ты ему туда еще Сфинкса предложи прикрутить, ага.

Тут только два адекватных решения, одно из них в [2], другое в [10]. В [13] - вариации. Эта задача настолько проста, что ее даже обсуждать скучно.

← →
Rouse_ © (2015-05-24 15:30) [24]

Нет у него полей - данные в памяти :)

← →
Inovet © (2015-05-24 15:49) [25]

Ещё раз подумал, с учётом
> в таблице есть индекс по ФИО, но translate и upper его убивают
А надо ли что-то городить в памяти, нет ли в ДБ2 возможности пострить подходящий индекс? Collate там какой-нибудь с учётом регистра и буквы "Ё". Пост 10 тоже о том.

Это всё то же продолжение любви с Пенсионным Фондом? А я сразу говорил, что проблем много, с первого взгляда неочевидных и мелких. Та же "Ё" в паспорте и "Е" в ПФ, и наоборот. "Дальновидные" разработчики её сначала запретили, потом разрешили.

← →
Pavia © (2015-05-24 18:19) [26]

> Остановись на секунду. У человека три поля, в каждом из
> них по одному слову максимум. Всего данных - несколько десятков
> мегабайт максимум. Какие нафиг токены, какой нафиг полнотекстовый
> поиск, какие нафиг документы? Ты ему туда еще Сфинкса предложи
> прикрутить, ага.Тут только два адекватных решения, одно
> из них в [2], другое в [10]. В [13] - вариации. Эта задача
> настолько проста, что ее даже обсуждать скучно.

Классическая заблуждение. На самом делеё всё наоборот. Хэш-таблицы не ускоряют поиск. Они ускоряют сравнения. А токены это и есть хэши. А ускоряет поиск индексирование. Вот когда токенов много там да хэши ускоряют поиск, но также в качестве токена можно использовать порядковые номера слов в словаре. При этом поиск в словаре вести линейно.

Хотя на java я бы просто создал ассоциативный массив благо реализация встроена. Да и построен этот массив на основе хэширования.

А что-бы доказать что вы ошибаетесь. Предлагаю вам самому составить полный алгоритм действия.

← →
Pavia © (2015-05-24 18:28) [27]

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

Хотя тут всего 3 слова. Так что число комбинаций мало и можно хэш-таблицы использовать.

← →
MsGuns © (2015-05-24 18:54) [28]

Не удержусь, тоже "ляпну" :)
DB2 достаточно быстрая СУБД. Тормоз наверняка в запросе, нельзя ли его увидеть полностью. Ну и эти ё и е, нельзя ли обойтись без них - в результсете не должно быть слишком много записей - можно и на клиенте отбросить лишнее.

Докладываю сообществу результаты.

Вначале то, о чем не упоминал ранее.

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

2. БД чужая, я в ней не хозяин. Поэтому любое изменение в ее структуре требует согласования (которого не всегда удается достичь). И это была вторая причина для того, чтобы попытаться ускорить работу, засосав все данные одним запросом (а не 10-ю тысячами) и дальше сравнивать на клиенте. Хотя, повторюсь, этот вариант очень нежелателен.

Что в итоге было сделано.

1. Конечно, был нужен индекс. К счастью, его удалось согласовать с владельцем базы. Построил индекс, основанный на функциях replace (вместо translate) и upper. Облом - не понимает DB2 function-based индексов, ругается. Скорее всего, из-за старой версии сервера - но уж какая есть, никуда от нее не денешься.

2. В таблицу было добавлено генерируемое поле с автозаполнением. В нем - конкатенация ФИО и все те же replace и upper. По этому полю и был построен искомый индекс.

==============

Результат - 5 минут. Что даже лучше, чем хотелось.

Всем спасибо.

Какой блин полнотекст.

Полнотекст - это поиск слов в неструктурированном тексте, желательно релевантно.

А тут прямое сравнение заранее типизированных структур (пусть и текстовых).

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

То есть, это как вместо

CompareText(s1, s2)

Взять и заюзать регулярку зачем то.

> Результат - 5 минут

Описка?? 5 минут или 5 секунд???

> jack128 © (25.05.15 01:44) [32]
>
>
> > Результат - 5 минут
>
> Описка?? 5 минут или 5 секунд???
>

Юра мечтал о 10 минутах вместо 50 минут.:)

Поиск по хеш таблице.

Я уверен, что если бы я задал такой вопрос, тот час был бы "отправлен" учиться :)

Простите не понял. Какие хеш таблицы? Поднять на клиента несколько миллионов записей, потом построить хеш и потом осуществлять поиск - за такое решение по голове погладят разве что кирпичом.
Решение добавить индексированное поле, содержащее поисковый ключ отчасти верное. Но имеет подводные камни.
Я бы рекомендовал добавить три поля в которых держать отдельно фамилию имя и отчество в верхнем регистре и очищенных от "мусора". Мусором кроме Е признал бы И Й пробелы, дефисы запятые и т. д.
Это позволило бы эффективнее искать, к примеру, по имени и фамилии без отчества

> Дмитрий С © (25.05.15 07:29) [34]

> если бы я задал такой вопрос, тот час был бы "отправлен" учиться :)

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

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

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

> Павел Калугин © (25.05.15 07:51) [35]

> Решение добавить индексированное поле, содержащее поисковый
> ключ отчасти верное. Но имеет подводные камни.

Паша, а какие ты видишь камни? Поделись, плз. Это может быть важно.

> Простите не понял. Какие хеш таблицы? Поднять на клиента
> несколько миллионов записей, потом построить хеш и потом
> осуществлять поиск

Например, завести поле с хешем фамилии и имени в таблице и индексировать его. Можно без заведения, некоторые субд такое позволяют.

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

Это хорошо. И хорошо, что получается. Тем не менее, меня бы все-равно отправили бы учиться :)

> Например, завести поле с хешем фамилии и имени в таблице
> и индексировать его.

Результат хэш-функции может быть одинаков для разных входных параметров.

>Павел Калугин © (25.05.15 07:51) [35]
>Я бы рекомендовал добавить три поля в которых держать отдельно фамилию имя и отчество в верхнем регистре и очищенных от "мусора". Мусором кроме Е признал бы И Й пробелы, дефисы запятые и т. д.
Это позволило бы эффективнее искать, к примеру, по имени и фамилии без отчества

Невнимательно читаешь. Юра в самом начале сказал, что база - чужая.
Кроме того, тебе, как опытному разработчику, нельзя не знать, что недостаточно просто "исправить" ошибки в базе РАЗОВО, надо еще менять бизнес-правила и, соответственно, политику пользовательских приложений, через которые в базу добавляется информация. А это уже совсем иная "опера".

Быстрый поиск комбинации строк в массиве Найти похожие ветки