[Закрыть]
 
popoff.donetsk.ua
Страсть теряет свою силу, как только стремление к ней становится осознанным.
Начало | Новости | Статьи | Форум | Опросы | Карта сайта | Обо мне
popoff.donetsk.ua - Клуппы Yato - Программирование - Модули - a - a.suffix
Я это делаю
Персональное меню
Голосование
Клуппы Yato Постоянный адрес этого вопроса
Деньги, но неинтересная работа и невозможность уделить время семье
Интересная работа, возможность саморазвиваться, но нищенский заработок
Ваш возраст (не обязательно)
Почему? (не обязательно)

Голосование закрыто.

Поиск по сайту
Реклама
Гинеколог, стоматолог, психотерапевт в Донецке
Статистика

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

Обсуждение статьи в форуме

21.12.07 13:32 fisha

Добрый день!
Меня заинтересовала ваша библиотека для работы с суффиксными деревьями, но, к сожадению, предлагаемый исходник имеет ряд синтаксических ошибок, таких как присутствие непарных фигурных скобок, цикл for без трех обязательных выражений и т.п. Возможно проблема в скрипте, который используется для отображения исходника. Надеюсь, эта достадная ошибка будет исправлена.

21.12.07 14:42 popoff

fisha,
Только что скачал и запустил скачанный с сайта скрипт. В качестве теста использовал тот тест, что записан в самом том файле. Всё работает, никаких ошибок, тем более синтаксических...

09.11.08 22:17 Sherman

Сделал простой враппер для сишной либы в виде php extension:

http://code.google.com/p/php-suffixtree/

Просмотреть все комментарии в режиме форума. Всего комментариев: 3