?

Log in

No account? Create an account
nyaload

Журнал Пушыстого

Журнал Пушыстого

Previous Entry Share Next Entry
suffix array sort
nyaload
_winnie
Как следует разобрался в алгоритме сортировки суффиксов. Написал более-менее читабельную и не сильно тормозящую функцию (легко переписывается на C). https://gist.github.com/dobrokot/ed1ae766ee6d90e50540

суффиксов
а суффиксов
в
вка суффиксов
иксов
ировка суффиксов
ка суффиксов
ксов
ов
овка суффиксов
ортировка суффиксов
ровка суффиксов
ртировка суффиксов
сов
сортировка суффиксов
суффиксов
тировка суффиксов
уффиксов
фиксов
ффиксов
Tags: ,


  • 1
Burrows–Wheeler transform?

Алгоритм используется как базовый кирпичик в фантастическом числе задач, но ты угадал, я сейчас разбирался именно в контексте BWT

def ss(txt):
  ii = sorted(range(len(txt)), key = lambda i : txt[i:])
  #return [txt[i:] for i in ii]
  return ii


На сях с указателями вообще тупо будет.
Или там именно кольцо текста нужно?


Я, честно говоря, впервые слышу про кольцо. По-моему, достаточно сортировать суффиксы. На то он и суффиксный массив. Другое дело, что сортировка в лоб вроде как в худшем случае квадратична относительно размера строки (на самом деле даже вроде n^2 log(n)). То бишь это далеко не оптимальный способ построения индекса.

Edited at 2015-04-02 02:08 pm (UTC)

Мне кажется, что закольцованность - нужна чисто для упрощения реализации алгоритма.
Вроде нет проблем переделать его под логику "после последнего символа как будто бы идут Особые Маленькие Символы", кроме замены A[i%n] на более сложные if для чтения из массива.

Вариант с key=... гораздо проще, спасибо.

Дополнить строку нулями - дурное дело нехитрое: text[i:] + chr(0)*(len(text)-i)

Мне кажется, что задачу можно было смело разбить на две:
- сортировка строк, к которым есть посимвольный доступ getchar(item_index,char_offset)
- применение этой сортировки к суффиксам одной строки getsuffix(text,i,c) = text[i+c]

Если просто взять и разбить, то алгоритм становится квадратичным на синтетическом примере "ababababab..." или на практическом примере "склеили две диссертации, одна из которых плагиат второй".

Edited at 2015-04-03 01:58 pm (UTC)

  • 1