Нуна бы найти patricia (C/C++), которая бы умела и на диск сбрасываться, а не только в памяти сидеть. На диск крайне желательно уметь сбрасываться в виде одного файла. Ну, максимум двух. Еще желательно, чтобы умела индекс подчитывать в память не целиком, а кусками. P.S. Может, кому пригодится: http://www.codeproject.com/string/pat_and_huff.asp - тут Хаффман предлагается сочетать с патрицией. Время вставки офигенно увеличивается http://www.codeproject.com/string/PatriciaTrieTemplateClass.asp - тут просто в памяти болтается
Пока постил, кажется, нарыли кое-чего: http://wikipedia-clustering.speedblue.org/trie.php http://wikipedia-clustering.speedblue.org/strBTree.php Если совместить этих двоих, то, возможно, как раз и получится то, что соответствует требованиям.
Про сериализацию, за давностью, не помню, но темплейтный PAT-класс долго обсасывался на RSDN (http://files.rsdn.ru/42491/PatriciaConts029.rar), какие-то исходники можно найти у Дэна Гасфилда - http://www.cs.ucdavis.edu/~gusfield/strmat.tar.gz (на русском был на book.ru, в сети не встречал) - это лучшее, что я вилел по деревьям, какая-то имплементация есть в исходниках 7z (IMHO, они нечитаемы) + http://kolchak.sdf-eu.org/res/simpat-0.10.tar.bz2
