a.suffix |  |
a.suffix - Модуль для работы с суффиксными деревьями
При помощи этого модуля можно:
Находить наибольшую общую часть одной, двух или более последовательностей за время О(m+n)
Проверять, является последовательность А непрерывной подпоследовательностью одной из последовательностей В, С, ... за время О(|A|) (без учёта времени на построение дерева, которое равно О(|B|+|C|+...)).
Пример использования:
<?php $a_suffix=a_suffix_create();
a_suffix_add($a_suffix,array(1,2,3,4,5,6,7,8,9,9,8,7,6,5,4,3,2),'first');
a_suffix_add($a_suffix,array(3,4,3,1,0,0,0,0,1,3,4,3,0,0,0,0,0),'second');
echo '<pre>';
$r=a_suffix_lcs($a_suffix);
print_r($r);
?>
Результат выполнения:
Array
(
[0] => Array
(
[id] => first
[c] => 9
[n] => 26
[p0] => 2
[p1] => 2
)
[1] => Array
(
[id] => second
[c] => 11
[n] => 26
[p0] => 0
[p1] => 2
)
[2] => Array
(
[id] => second
[c] => 11
[n] => 26
[p0] => 9
[p1] => 2
)
[3] => Array
(
[id] => first
[c] => 9
[n] => 28
[p0] => 14
[p1] => 2
)
[4] => Array
(
[id] => second
[c] => 11
[n] => 28
[p0] => 1
[p1] => 2
)
[5] => Array
(
[id] => second
[c] => 11
[n] => 28
[p0] => 10
[p1] => 2
)
)
Скачать исходник библиотеки:
http://popoff.donetsk.ua/file/text/libs/a.suffix.php
Смотрите также
Суффиксные деревья на algolist.ru:
http://algolist.manual.ru/search/lrs/suffix.php
Суффиксные деревья в русской википедии:
http://ru.wikipedia.org/Суффиксное_дерево
Последняя модификация: 25.11.07 15:21 q Обсуждение статьи в форуме Не проходите мимо! Оставьте Ваш комментарий в форуме! >>> Добрый день!
Меня заинтересовала ваша библиотека для работы с суффиксными деревьями, но, к сожадению, предлагаемый исходник имеет ряд синтаксических ошибок, таких как присутствие непарных фигурных скобок, цикл for без трех обязательных выражений и т.п. Возможно проблема в скрипте, который используется для отображения исходника. Надеюсь, эта достадная ошибка будет исправлена. fisha,
Только что скачал и запустил скачанный с сайта скрипт. В качестве теста использовал тот тест, что записан в самом том файле. Всё работает, никаких ошибок, тем более синтаксических... Просмотреть все комментарии в режиме форума. Всего комментариев: 3
Не проходите мимо! Оставьте Ваш комментарий в форуме! >>> Цитирование материалов моего сайта приветствуется! при условии видимой действующей! гиперссылки на мой сайт. [Ссылки] Если Вы нашли опечатку на этой странице, пожалуйста, выделите ее мышью и нажмите Ctrl+Enter. Сделаем язык чище! (c) Yuri Popoff, 2004 - 2008, popoff.donetsk.ua, style.donetsk.ua
|
|
