Если текст представляет собой набор случайных постоянно...14.09.05 12:40 Число просмотров: 3432 Автор: DPP <Dmitry P. Pimenov> Статус: The Elderman Отредактировано 14.09.05 12:42 Количество правок: 1
> Есть много строк и надо структуру данных, которая позволила > бы эффективно искать подстроку сказу во всех этих строках и > получать список вхождений (точнее только номера исходных > строк, смещение не надо).
Если текст представляет собой набор случайных постоянно меняющихся символов, то придется полным перебором.
Мне тут пришла в голову прикольная мысль. Предлагаю построить табличку по всему набору исходных строк таким образом - перебрать все пары рядомстоЯщих байт. Из них сформировать ключ путем умножения второго байта на 256 и добавления первого. Местоположение этой пары в тексте (строка, позиция) приписать к этому ключу. В худшем случае получим 64к ключей и в четыре раза больше байт координат, чем байт текста. При поиске вычисляем ключ по первым байтам искомого фрагмента и обходим только координаты тех фрагментов, которые начинаются с этой пары байт. Скорость поиска возрастет примерно в 64к раз при нормальном распределении.
А что, настолько большой набор огромных строк и тормознутый процессор, что простой поиск занимает много времени?
> Помню что была такая классная штука, называлась чтото вроде > сжатого дерева с суффиксными ссылками, но вот никак не могу > найти его описания. Кто знает эту структуру или может дать > ссылку на описание - пожалуйста в студию.
Есть много строк и надо структуру данных, которая позволила бы эффективно искать подстроку сказу во всех этих строках и получать список вхождений (точнее только номера исходных строк, смещение не надо).
Помню что была такая классная штука, называлась чтото вроде сжатого дерева с суффиксными ссылками, но вот никак не могу найти его описания. Кто знает эту структуру или может дать ссылку на описание - пожалуйста в студию.
суффиксное дерево14.09.05 15:47 Автор: paganoid Статус: Member
Если текст представляет собой набор случайных постоянно...14.09.05 12:40 Автор: DPP <Dmitry P. Pimenov> Статус: The Elderman Отредактировано 14.09.05 12:42 Количество правок: 1
> Есть много строк и надо структуру данных, которая позволила > бы эффективно искать подстроку сказу во всех этих строках и > получать список вхождений (точнее только номера исходных > строк, смещение не надо).
Если текст представляет собой набор случайных постоянно меняющихся символов, то придется полным перебором.
Мне тут пришла в голову прикольная мысль. Предлагаю построить табличку по всему набору исходных строк таким образом - перебрать все пары рядомстоЯщих байт. Из них сформировать ключ путем умножения второго байта на 256 и добавления первого. Местоположение этой пары в тексте (строка, позиция) приписать к этому ключу. В худшем случае получим 64к ключей и в четыре раза больше байт координат, чем байт текста. При поиске вычисляем ключ по первым байтам искомого фрагмента и обходим только координаты тех фрагментов, которые начинаются с этой пары байт. Скорость поиска возрастет примерно в 64к раз при нормальном распределении.
А что, настолько большой набор огромных строк и тормознутый процессор, что простой поиск занимает много времени?
> Помню что была такая классная штука, называлась чтото вроде > сжатого дерева с суффиксными ссылками, но вот никак не могу > найти его описания. Кто знает эту структуру или может дать > ссылку на описание - пожалуйста в студию.
Не слышал о такой.
Ну, допустим эдак миллиона 3 строк, каждая по 100-200 байт...14.09.05 23:47 Автор: KUV Статус: Незарегистрированный пользователь
подробно о проекте
Анализ криптографических сетевых...
новое сообщение
закрытая нитка
новое сообщение
в закрытой нитке
старое сообщение
