Иван FXS
в частности, - делает ли кто-нибудь подобные индексы?
Подобные - подобным алгоритмом, или подобные - уникальные индексы для фиксированного набора строк?

На самом деле это какие-то странные индексы :)

На счёт эффективности такого хранилища, тоже есть сомнения.
На каждом шаге деления, кол-во текстов требующих уникальный ключ растёт как 2^n. Если тексты в "контенте" действительно большие, то кол-во строк проиндексированных "просто так" не плохо разрастётся, пока не начнут появляться одинаковые фрагменты текста.

Опять же, выбор терминальных символов не тривиальная задача.

Если хеш-функции описанной в п.3 нет и задавать последнюю путём перечисления, то процесс вычисления хеш-функции сильно усложнится.
Фактически придётся фиксировать правило разбияния строки "пополам" и каждую строчку разбивать до терминальных символов, а потом в обратном порядке восстанавливать хеш, пробегая для этого по списку всех пар (key1, key2), короче мало приятного.

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

Эффект сжатия достигаемый за счёт кодирования терминальными символами (если цель экономия памяти и т.п.) можно обеспечить и по другому. Например, при помощи статического алгоритма Хафмана. По крайней мере будет уверенность, что сжатие оптимально, в отличиии от выбора терминальных символов от балды.

Хранить тексты в виде древовидных структур (леса) тоже никто не запрещает.
Для текстов, где действительно много общих частей, получим экономию.
Однако при этом индексировать промежуточные узлы деревьев нет необходимости (что происходит в описанном алгоритме).

Такие индексы могли бы прокатить для поиска подстрок, если терминальные символы были бы примитивами (буквами, знаками припинания). Но про эффективность/не эффективность такого алгоритма говорить не стану :)

Кроче говоря, исходный алгоритм, это три задачи в одной, и чем он лучше решения трех задач по отдельности не ясно :)

---

Выше написанное, это поверхностный взгляд на вопрос. В полне возможно, что в чём-то я не прав :)


И дальше - как можно такие индексы ИСПОЛЬЗОВАТЬ? Акромя как - в качестве ХРАНИЛИЩА строк ...

Обычно сначала ставят задачу, а потом ищут её решение, а не на ходят какое-то решение и думают потом для какой же оно задачи.
Хотя всякое бывает :)

Иван FXS NotGonnaGetUsНа каждом шаге деления, кол-во текстов требующих уникальный ключ растёт как 2^n. - на каждом шаге растёт в два раза, - Вы, наверное, это хотели сказать?

Именно это мы и сказали.


NotGonnaGetUsЕсли тексты в "контенте" действительно большие, то кол-во строк проиндексированных "просто так" не плохо разрастётся, пока не начнут появляться одинаковые фрагменты текста.- дык, мы же не хаос собирается индексировать, а ЧЕЛОВЕЧЕСКИЕ тексты ... есть ПРЕДПОЛОЖЕНИЕ, что "одинаковых фрагментов текста" там довольно много ...

Да хоть набор букв.
В текстах часто могут повторяются "слова", а не "наборы слов" - т.е. группы предложений, предложений, части приложений.


NotGonnaGetUsЕсли хеш-функции описанной в п.3 нет ... А если такая хеш-функция есть, то почему бы её и не использовать в качестве ключа?- хеш-функция ЕСТЬ, именно она и используется в качестве ключа.

У нас разногласие в терминах.
Хеш-функция вычисляется для любой строки и даёт в общем случаее не уникальное значение - т.е. восстановить строку по занчению хеш-функции нельзя.
Ключ - уникальный идентификатор. Он взаимнооднозначно связывается с набором каких-то объектов.

NotGonnaGetUsЭффект сжатия достигаемый за счёт кодирования терминальными символами ...- основной "эффект сжатия" я предполагаю достигаемый не за счёт терминальных символов, а за счёт наличия "одинаковых фрагментов текста".

Я же не говорил, что это основной эффект - так? Про деревья отдельный разговор.


NotGonnaGetUsХранить тексты в виде древовидных структур (леса) тоже никто не запрещает. Однако при этом индексировать промежуточные узлы деревьев нет необходимости (что происходит в описанном алгоритме).- не понял: а как их - тогда - идентифицмровать???

?
Лес служит для хранения строк.
Вершина дерева идентифицирует строку.
Строка идетифицируется ключём.
Ключ -> вершина -> строка.


А если серьезно - насчет задачи ... без всякого сомнения, присутствует задача ... ммм ... социолингвистики: посмотреть - статистически - какие строки (не слова, а ... что-то намного более длинное) насколько часто встречаются в ... окрухающих нас контентах. Ну и - семантикая всякая ... сети семантические и прочее ...
Забавно. Я на этот алгоритм смотрел с других позиций :)

Иван FXS- не очень понял, с чем и о чем Вы - в этом месте полемизируете ...
Но я-то как раз считаю, что НЕ ТОЛЬКО слова, но и "наборы слов" в ЧЕЛОВЕЧЕСКИХ ... ммм ... потоках символов часто повторяются:
намного чаще, чем они повторялись бы в "хаотических" потоках.

Я не обсуждаю человеческие ммм потоки. Речь об вашем алгоритме :)
Он выделяет не одинаковые "наборы слов", а "половины текстов". Тексту придётся раздробиться до уровня слов, пока не начнутся массовые повторения. Это моя "интуиция" если вам так угодно :)


- разногласие в терминах - наверное ...
...
Например, MD5 ... дайджест длиной 128 бит ... какова для него ЗНАЧИМОСТЬ коллизий?

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


- как ССЫЛАТЬСЯ на ветки, если им не присвоены ИДЕНТИФИКАТОРЫ? Вот о чем было мое недоумение! Мы же должны записать ТРОЙКУ ( key,key1,key2 )!
По вашему утверждению key0 уникален. Какие проблемы в том, что бы пометить им вершину?