Previous Entry Share Next Entry
2016-01

ходим кругами

В который раз я с удивлением переоткрываю, что для спокойствия души и вообще sanity мне жизненно необходимо хотя бы несколько дней в год сидеть ночью в ПУСТОЙ квартире. В тишине.

А потом снова забываю. Ну блииииин.

Совсем unrelated: а есть какие-нибудь очень-compressed lossy inverted index'ы для приблизительного полнотекстового поиска? ну типа чтобы занимали не 2х и не 8х от оригинального текста, а, например, 0.1х. А лучше 0.01х.

Можно чтоб давали false positives, хуже если false negatives, позиции в тексте не нужны, TF-IDF можно выбросить, но с ним лучше.

Хорошо, если их можно динамически апдейтить (добавлять и удалять документы). Если нельзя - нууу, будем делить документы в бины, отделять hot от cold, то-се.

Совсем хорошо, если можно части индекса отдельно строить и мержить.

Важно, чтобы RAM мало требовалось на построение и поиск (условно, датасет весит 1 гб, документы 1 кб..5 мб логнормально распределены, есть 50-200 мб диска, 20-50 мб оперативки). Пока думаю про какое-то trie толстых блумфильтров, где документы в листьях, а вверх они OR-ятся, группированы просто от фонаря (по старшим битам например)

Вотъ..

This entry was originally posted at http://wizzard.dreamwidth.org/377977.html. It has comment count unavailable comments. Please comment there using OpenID.

  • 1
kray_zemli June 27th, 2014
Тоже подумал про bloom-фильтр для множества хэшей всех отрывков из N подрядж идущих символов.

nponeccop June 27th, 2014
ага. Rabin-Karp.

lev June 27th, 2014
отрендерить мелким шрифтом, упаковать жпегом

kodt_rsdn June 27th, 2014
Марковскую сеть построить?
Будет считать вероятность вхождения данной цепочки слов в тот или иной класс (документ).

kodt_rsdn June 27th, 2014
Вообще, задача классификации в ASR возникает. В понедельник пороюсь в библиографии, может, чего практичного найду.

kurumpa June 27th, 2014
А представляешь, пару дней посидеть в пустых горах? ммм....

nponeccop June 27th, 2014
пару лет посидеть в пустой стране - вот мой ответ!

sa1amanteri June 27th, 2014
Мне для стабильности психики нужно несколько раз в неделю быть одной в квартире. Только днём, потому что вечером мне становится грустно, когда никого нет.
Но и это получается не всегда)

_winnie June 27th, 2014
Можно попробовать сначала без "вероятностных" структур данных, а сколько данных ты хочешь хранить.

Хранение одного doc-list для одного слова занимает как минимум Log2( Binom(n, w) ) битов. Эта формула аппроксимируется на практике "короткие док-листы храним как списки, длинные как bitset", т.е. min(w*log(N), N). Или хранят дельты между doc-id вместо самих doc-id. Так или иначе, это попытка приблизить логарифм бинома.

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

Возможно, ты захочешь выкинуть stop-слова.
Сколько получится?


Edited at 2014-06-27 11:18 am (UTC)

wizzard0 June 27th, 2014
> слова встречаются независимо друг от друга в документах
Эээ, в смысле?

_winnie June 27th, 2014
В том смысле, что не пытаемся ужать два doc-list "нуф-нуф" и "наф-наф" за счет того, что один хорошо повторяет другой.
Или что наличие слова "cat" в документе означает что в нём скорее всего нет русских слов.


Edited at 2014-06-27 01:37 pm (UTC)

  • 1
?

Log in

No account? Create an account