Организация структуры данных

[[DAN]]

Огранизация структуры данных

Всем привет!
Имеется следующее:
*) Есть три строки; каждая длиной не более 3 символов
*) Эти 3 строки идут последовательно одна за другой.
*) Первая строка содержит как минимум 1 символ; оставшиеся две строки могут быть нулевой длины
*) Если вторая строка пустая, то третья строка тоже пустая.
*) Если вторая строка не пустая, третья может быть как пустой, так и не пустой
*) Все символы являются числами от 0 до 9

*) + Дана символьная строка длиной от 4 до 16 символов (включительно). Все символы - числа от 0 до 9


Необходимо:
Организовать структуру данных для хранения в БД, такую, чтобы обеспечить максимально эффективный поиск.

Критерий поиска такой:
В строке длиной 16 символов найти максимальное вхождение комбинации из трехсимвольных строк.
Трехсимвольные строки конкатенируются строго по порядку (без комбинаций).

Поиск в "длинной" строке должен вестить строго с первого символа.

Пример:
Три строковых триплета:
1) "264" "" ""
2) "264" "811" ""
3) "264" "811" "1"

и имеется строка "264811234567"
Тогда самый длинный триплет, который входит в эту строку, будет под номером 2.

Да, эти строковые триплеты хранятся в БД (PostgreSQL). Повторюсь, поиск вхождения триплета в данную "длинную" строку должен быть максимально быстрым.

Если есть идеи по организации данных и алгоритму (запросам к БД) поиска, буду рад их услышать!

 

[Falc]

[DAN]
Откусывай с конца строки по символу и ищи.
По индексам быстро будет.

Можно все в один запрос через OR засунуть, а потом а потом из найденых выбирать самый длиный триплет.

 

[[DAN]]

Falc
с конца откусывать отпадает.
В среднем вхождение составляет 5 символов. Отрубать с конца как-то неправильно.
К тому же база строковых триплетов не маленькая (~ 15.000 записей)

 

[Falc]

[DAN]
>>В среднем вхождение составляет 5 символов. Отрубать с конца как-то неправильно.
Следовательно в среднем 4-е поиска ключевого поля (не забыть поставить уникальность)
В мускуле это меньше 0.001 с

 

[su1d]

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

и запрос на поиск уже делать не в основной таблице, а в дополнительной.

а "длинная строка" -- очень длинная?

непонятно что будет быстрее:
- один поиск типа long_string LIKE '%'.codes.'%';
- несколько поисков codes_length <= LENGTH(long_string_part) AND long_string_part LIKE codes.'%'; где long_string_part -- "длинная строка" каждый раз без первого символа.

в последнем будет использоваться индекс. в первом -- нет.

 

[[DAN]]

Как вариант, можно "склеить" трехсимвольные строки в одну и объявить ее индексом.
Но от этого выборка ненамного ускорится.

su1d
идею про длину строки стоит обдумать.
Длина "длинной" строки до 16 символов, и эта строка заведомо длиннее, чем конкатенация трехсимвольных строк. Еще раз отмечу, что "короткие" строки (назовем их коды) склеиваются однозначно по порядку, т.е. комбинация из трех кодов всегда одна. Перестановок там никаких не будет. Каждый триплет кодов уникален.

По LIKE искать будет долго, этот вариант сразу отметается.

Была идея организовать коды в виде древовидной структуы. Потому как от первого кода зависит второй, от второго третий.
Но опять же непонятно, как производить поиск в этом дереве.
Дело в том, что неизвестно, сколько символов надо отрезать от "длинной" строки, чтоб сравнить их с 1-м кодом, потом со 2-м (если есть) и т.д.
Получится, что нужно будет произвести 3 запроса (в 1 символ, в 2 и в 3 символа, отрезанных от начала "длинной" строки) для того, чтоб найти совпадение по первому коду, потом еще 3 запроса для второго кода и 3 для 3-го.
9 запросов для идентификации одной "длинной" строки - это слишком круто. Хотя в этом случае сужается множество для поиска.

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

Falc
Помимо размера таблицы в real-time надо будет прокручивать от 10 до 10^7 запросов. Это тоже существенно.

 

[Falc]

[DAN]
>>Поиск в "длинной" строке должен вестить строго с первого символа.
Погоди, разве это не значит что надо искать только по LIKE 'xxx%'

 

[crocodile2u]

У меня вопрос по уточнению задачи:

Если имеются три строковых триплета:
1) "264" "81" "1"
2) "264" "8" "11"
3) "264" "811" "", они что, идентичны для поиска (насколько я понял, так оно и есть)? Если это так, то, по-моему, нужно хранить одно большое число, а не три маленьких.

 

[[DAN]]

crocodile2u
Таких вариаций не будет. Большое число (строка) тоже хранится, можно и его вхождение искать (см. пост su1d'a)

Falc
Значит, но не то.
Скажем, у нас в БД хранится строка вида "264811". Одна из многих.
На вход программы пришла "длинная" строка вида "26481134234".
Нам надо определить, что именно эта строка ("264811") имеет самое длинное входжение в поступившую на вход строку ("26481134234").
Каким образом тут фигурирует LIKE, я не соображу :/

 

[Falc]

[DAN]
Лайк тут в обратную сторону.

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

 

[[DAN]]

string LIKE pattern
=> в обратную стороу не катит

 

[Falc]

[DAN]
Так, чтоты мы запутались.

Спрашиваю еще раз чтобы найти нужный триплет достоточно сделать сравнения
triplet% LIKE $String ?

или же надо:
%triplet% LIKE $String

Если первое, то чем тебя не устраивает мой способ описаный в первом посте?

 

[[DAN]]

первое.
Не устраивает то, что запросов будет много.
Хотелось бы одним запросом вытащить.

 

[Falc]

[DAN]
Делай одним

 

[[DAN]]

Оказалось, что быстрее всего работает запрос вида [sql]SELECT max(code) FROM codes WHERE code IN (2, 26, 264, 2648, 26481, 264811)[/sql]при услови, что все триплеты мы перегоняем в числовой вид.
Время на выборку составило < 10 мс против 30-80 мс для запроса с LIKE.
Всем спасибо!

 

[su1d]

в Постгресе же SELECT MAX(field) работает вроде бы медленнее, чем SELECT field FROM ... ORDER BY field DESC LIMIT 1 ?

 

[[DAN]]

su1d ОГРОМНОЕ (!) спасибо за наставление на путь истинный )))
Работает быстрее, раз в 10-30

 

[su1d]

да я чё, я ничё...
я сам только неделю, как на Постгрес перелез =)

 

[Falc]

[DAN]
О чем я тебе и говорил. А ты все слушать не хотел.

 

[[DAN]]

Falc так ведь не через LIKE же
А про IN я что-то совсем забыл. Вчера сел перечитывать SQL2 и с удивлением обнаружил эту прекрасную операцию ))

su1d Постгрес рулит !!!