Как устроен n-gram индекс?

то как обычно делают?

А ты объясни что у тебя есть и чего ты хочешь добиться.

"собака воет всюду" : ngram_id = 555 // id фразы для ссылки на неё
"бакланы всюду" : ngram_id = 666 // какая-то другая ngram

собака - 555
собака воет - 555//зачем?
собака воет всюду - 555//зачем?
воет - 555
воет всюду - 555//зачем?
всюду - 555, 666 // две ссылки

Почему не работает это?

"собака воет всюду" : ngram_id = 555 // id фразы для ссылки на неё
"бакланы всюду" : ngram_id = 666 // какая-то другая ngram

собака - 555
воет - 555
всюду - 555, 666
бакланы - 666

и сохраняют все перестановки или просто делают 2 отдельных поиска для 2 отдельных слов в запросе?

По мне так получить из двух поисков: {{555, 666}, 555} и уже что-то с этим делать проще и быстрее, но я не шарю в твоей теме. Тут уже можно считать кол-во совпавших и прочее.

Как оно будет лежать в n-gram индексе?

Почему вы показываете это не на токенах, а собственно на фразах. Это же не этично.
По поводу самого хранения n-gramm в индексах. Здесь все зависит от реализации. Возьмем, скажем, ES. Зададим токенайзер скажем от 2 до N. Где N длина максимального токена в будущем нашем словаре. Возьмем, скажем, для примера слово «кукареку». Макс. длина N, сл-но, будет равняться 8.
Почему именно «кукареку»? Мы выбрали мин. длину грамма - 2. Значит у нас будет 2 повторяющихся грамма КУ вначале, и КУ в конце. Сейчас мы увидим что ES хранит оба этих грамма, более того она хранит и начальное и конечное положение смещения обоих. Для начала проанализируем сами граммы:

[snaik 01:30:18 ~] curl 'localhost:9200/test/_analyze?pretty=1&analyzer=mna' -d 'кукареку' | grep "\"token\""
    "token" : "ку",
    "token" : "кук",
    "token" : "кука",
    "token" : "кукар",
    "token" : "кукаре",
    "token" : "кукарек",
    "token" : "кукареку",
    "token" : "ук",
    "token" : "ука",
    "token" : "укар",
    "token" : "укаре",
    "token" : "укарек",
    "token" : "укареку",
    "token" : "ка",
    "token" : "кар",
    "token" : "каре",
    "token" : "карек",
    "token" : "кареку",
    "token" : "ар",
    "token" : "аре",
    "token" : "арек",
    "token" : "ареку",
    "token" : "ре",
    "token" : "рек",
    "token" : "реку",
    "token" : "ек",
    "token" : "еку",
    "token" : "ку",

[snaik 01:33:36 ~]curl 'localhost:9200/test/_analyze?pretty=1&analyzer=mna' -d 'кукареку'
{
  "tokens" : [ {
    "token" : "ку",
    "start_offset" : 0,
    "end_offset" : 2,
    "type" : "word",
    "position" : 0
  }, ... {
    "token" : "ку",
    "start_offset" : 6,
    "end_offset" : 8,
    "type" : "word",
    "position" : 27
  } ]
}

А фраза ранве не является n-граммой? Во фраpе грамма — это слово. В ДНК грамма — это будет нуклеотид какой-нибудь. n-грамма для меня — это цепочка чего-нибудь.

Почему. Строго говоря является, там может храниться любая последовательность символов. Я говорю лишь о том, что

Это же не этично.

Если вы реализуете поиск, все же вы должны применять это лишь на токенах в виде слов. Безусловно еще лучше, если перед применением n-gramm-анализатора, вы будете применять все остальные в порядке их важности для поиска. От собственно разделителя и lowercase до морфологии/snowball/stopwords, причем на все нужные языки. Хотя вы и правы в том, что токеном может быть все что угодно, но для реализации возможных видов поиска, это лучший и проверенный вариант. Ну и конечно, все зависит от языка. Насколько вы знаете, в том же китайском редко разделяют слова, и часто пишут целыми предложениями. Там на вхдо n-gramm-анализатору зачастую приходят предложения что называется «как есть». Но если мы вернемся к родному языку, то все же лучше, когда n-gramm применяют уже на «обработанных» токенах. Т.е. фактически фраза:

Обожаю запах напалма по утрам!

в n-gramm-анализатор должна прийти в виде массива подготовленных токенов (при учете морфологии вместо snowball):

    {обожать, запах, запахнуть, напалм, утро}

А фраза ранве не является n-граммой?

Да, безусловно любая последовательность символов может представлять собою грамм, но нужно понимать в контексте чего мы говорим. Для чего вы хотите это реализовать, вот в чем вопрос? Может быть и не для поиска вовсе, просто я привык говорить о них в одном контексте. Хотя смысл один, и я уже дал его в первом своем комментарии:

Здесь все зависит от реализации.

Я не понял критику по поводу моего «фраза является n-граммой». Вы ведь тоже заюзали фразу из слов «обожаю запах напалма по утрам» и роль грамм у вас исполняют слова в фразе. Что за наезд на фразы?

Во-первых, никаких наездов нет. Я уже неоднократно вам сказал что в моем случае в виде грамм хранятся части токенов (конкретно здесь, слов), и сама фраза никакой связи с n-gramm-анализатором не имеет. В вашем случае говорить «фраза является n-граммой» по меньшей мере не этично. Граммом (читайте частью) может являться «собака», «собака воет» и т.д. и т.п. Но изначальная ваша фраза, если можно так выразиться, всего лишь черной материал. Необработанный ствол дерева, если будет угодно. А n-gramm-анализатор это лесопилка. И вот конечный результат обработки, повторюсь, будет зависеть от реализации алгоритма обработки. Сейчас ваши фразы и примеры из ОП звучит по меньшей мере странно. И единственное на что можно ответить, так это на последний вопрос:

Перемешивают все граммы в n-грамме и сохраняют все перестановки или просто делают 2 отдельных поиска для 2 отдельных слов в запросе?

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

Простите за тупость, я быдло, разговариваю как умею )

Спасибо за пояснения. Вопрос тупо по терминологии: а что обычно понимают под ngram-индексом? Это индекс, который по какому запросу что должен вернуть? Т.е. хочу услышать общее определение (ваше, не из википедии), а потом может быть пару примеров.

Область применения n-gramm последовательностей огромна. Но лично мы применяем его только в реализации алгоритма поиска. Конкретно для так называемого «prefix matching» (префиксного совпадения), и для «partial matching» (частичного совпадения). Первое много где обозначается как autocomplete. Т.е. на запрос «м» среди токенов «мама», «мыла» и «маникен», получаем:

мама -> 2 совпадения (len 4), релевантность = 3

мыла -> 1 совпадение (len 4), релевантность = 2

маникен -> 1 совпадение (len 7), релевантность = 1

Это достигается благодаря edge n-gramm. В основном это граммы с длиной от 1 до 2.
Второе (partial matching) часто применяется для реализации алгоритма «поиска с ошибками» (раньше мы использовали для этого расстояния Дамерау-Левенштейна, но уже год как отказались). Т.е. на запрос «сегореты» среди токенов «сигареты», «ракеты» и «рейтузы», получаем:

си га ре ты -> 2 совпадения (len 8), релевантность = 3

рей ту зы -> 1 совпадение (len 7), релевантность = 2 (т.е. совпадение грамма в начале токена выше по приоритету для релевантности, нежели длина токена)

ра ке ты -> 1 совпадение (len 6), релевантность = 1

Ну а это достигается благодаря стандартным n-gramm последовательностям, в основном (в разных проектах по разному) от 2 до N (где N длина наибольшего токена в словаре). Т.е. фактически получается что на n-gramm последовательности разбиваются как токены для хранения в конечный индекс, так и сами запросы для поиска по индексу. Но возможностей для применения n-gramm-последовательностей на самом деле очень много. Вот, можете посмотреть базу n-gramm GR, судя по статье они использовали ее много где:

http://googleresearch.blogspot.ru/2006/08/all-our-n-gram-are-belong-to-you.html

we have been using word n-gram models for a variety of R&D projects, such as statistical machine translation, speech recognition, spelling correction, entity detection, information extraction, and others.

Блин, какой классный пост, вот бы с вами в баре затусить)

Пока только 1 тупой вопрос: т.е. Левенштейн дороже чем ngram-ный подход, и в высоконагруженных поисках Левенштейн уступает ему?

Перечитаю пост ещё несколько раз...

Левенштейн дороже чем ngram-ный подход, и в высоконагруженных поисках Левенштейн уступает ему?

Нет, разумеется. Расстояния Дамерау-Левенштейна намного дешевле при любом подходе. Хотя-бы потому что нет избыточного индекса. Но их кроме как для ошибочного поиска мало где применишь. N-gramm все же более универсальные.

вот бы с вами в баре затусить)

Милости просим, как будете в Челябинске, пишите :)

В Челябинске я жил до 2007, у нас много общего)