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

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

Поиск по сайту
Реклама
Программное обеспечение любой сложности
koins.com.ua
Статистика

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
Не проходите мимо! Оставьте Ваш комментарий в форуме! >>>