Всем доброго времени суток. Занялся влотную алгоритмами... 1. Мне не совсем понятно, как строить и хранить бинарные деревья. Т.е. предположим есть дерево: X ^ | 1 | |\ | | \ | 0 1---- | |\ \ \ | 0 1 0 1 | |\ |\ |\ |\ .......................... | +------------------>Y 0 Каким образом его лучше сохранить в памяти...? Только лишь в 2х мерном массиве или можно как-то компактнее...? Поскольку незанятые области будут нулевые, а мне нужна максимаьная экономия. 2. Где можно прочитать про деревья, кроме Кнута и википедии? Гугл перерыл... 3. Мне не совсем очевидно, за счет чего деревья увеличивают скорость поиска последовательностей... К примеру, если дерево еще не построено, а последовательность нужно найти за один проход... В общем, накидайте инфы, заранее благодарен
1. Дерево в массиве не поможет? 2. Кормен? 3. За счёт их упорядоченности. Читай Кормена и Кнута, у них приведены соответствующие доказательства. Что ты имеешь ввиду? Если дерево не достроено, то в нём поиск возможен так же, как и в полностью построенном дереве. В противном случае как же ты хочешь искать в дереве то, чего ещё в нём нет?
IceStudent респект Еще вот один момент Предположим есть текст y = "ТЕКСТАБРАКАДАБРАТЕКСТ" Нужно построить дерево для оптимизации поиска. Например мы подаем на вход функции x = "АБРА" а на выходе получаем: 1 - если y сожержит x 0 - если нет. Тут как, прийдется x и y рассматривать как последовательности бит, далее построить бинарное дерево по битам? Или можно оперировать непосредственно с символами? ЗЫ: не пинайте за ламерство - я только учусь.... )
Мне кажется, ты не туда полез. Бинарные деревья используют в словарях, когда есть список слов и нужно найти слово в нём. У тебя же поиск подстроки, а для этого есть другие алгоритмы (имхо).
nitrotoluol Подстроки хорошо ищет следующий алгоритм. Берём буфер, который нужно сжать. проходим по нему и создаём массив указателей на массив указателей на все пары символов. Т.е. PPWORD Pointers = {p0000,p0001,...,pffff} где p0000 - массив указателей на все места, где в исходном массиве встречпается 0x0000 (Ясно дело все массивы динамические) Теперь допустим ты хочешь найти все фразы, совпадающие с искомой на 2 и более символа -> первые 2 символа у них совпадают. Берём эти 2 символа как индекс в массиве Pointers и получаем указатель на массив указателей на все фразы в тексте, по коротым нужно искать. для lz 30 - 50 ближайших фраз проверить вполне достаточно. Ещё следует проверить массивы p0000 .... на то, чтобы у в них не было длинных цепочек укеазателей, которые отличаются на 1. Для LZ всё равно от этого пользы нет. Память жрётся прилично, но вполне приемлемо. Так же можно заполнять массивы p0000... по мере того, как будет сжиматься текст, а не перед его сжатием. Но это уже детали.
nitrotoluol Если тебе нужен именно поиск подстроки в строке, то вполне можно обойтись без деревьев - например, с помощью Z-функции за O(length(S1+S2)), т.е. за линейное время (см. алгоритм Кнута-Морриса-Пратта).
