Уконенов алгоритам

С Википедије, слободне енциклопедије
  • У информатици, Уконенов алгоритам ради у линеарном времену, мрежни алгоритам за конструисање суфикса дрвета, предложено од стране Еско Укконен-а, 1995.

Алгоритам почиње са имплицитним суфиксом стабла које садржи први карактер стринга.

  • Онда кораке кроз низ додајући узастопне знакове док дрво не заврши. Ова наредба додавање карактера даје Укконен алгоритам своју "мрежну" имовине. Ранији алгоритми кретали су уназад од последњег знака ка првом, тј. од најдужег до најкраћег суфикса, или од најкраћег до најдужег суфикса. Наивна имплементација за генерисање суфикс дрвета захтева O(n²) или чак O(n³) време, за константне величине писма, где је n дужина низа.
  • Коришћењем више алгоритамске технике, Уконен-а сводимо на O(n) (линеарно),време за константне велицине алфабета, и O(n log n) уопште.

Референце[уреди | уреди извор]

Планови за будућност:[уреди | уреди извор]

  • Рефактор да имају мање глобалне варијабле
  • Поновно коришћење Јава 'хасх'

Додатна литература[уреди | уреди извор]

Спољашње везе[уреди | уреди извор]