Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
suffix array sort
def trivial_suffix_sort(txt):
n = len(txt)
txt2 = txt + txt
tmp = sorted((txt2[i:i+n], i) for i in xrange(n))
return [x[1] for x in tmp]
def suffix_sort(txt):
# рассматривает txt как кольцо, и сортирует строки txt[i:i + len(l)],
# возвращает список индексов sort_permutation[i], где начинается i-ая сортированая строка
# см. также эквивалентную функцию trivial_suffix_sort
# для сортировки именно как суффиксов можно приклеить "самый маленький символ" в конец
# чтобы разобраться в этом коде, нужно хорошо понимать алгоритм radix sort
n = len(txt)
group_start = [0] * max(n, 256)
sort_permutation = [0] * n
group = [0] *n
ptmp = [0] * n
group_tmp = [0] * n
# сортируем подстроки по первому символу
for ch in txt:
group_start[ord(ch)] += 1
prev = 0
for i in xrange(len(group_start)):
#конвертируем количество символов в индекс начала записи
group_start[i], prev = prev, prev + group_start[i]
group_start_saved = list(group_start) #ещё понадобится
for i, ch in enumerate(txt):
j = group_start[ord(ch)]
sort_permutation[j] = i
group[i] = ord(ch)
group_start[ord(ch)] += 1
group_start = group_start_saved
#инвариант цикла:
#sort_permutation - сортированные подстроки длины l (i-тая строка в сортированом массиве - txt[sort_permutation[i]:sort_permutation[i]+l])
#group - класс эквивалентности этих подстрок,
# txt[i:i+l] меньше/больше/равно txt[j:j+l] <=> group[i] меньше/больше/равно group[j],
# формируются как номер группы одинаковых подстрок (но на первой итерации - просто номер символа)
#group_start - в какое место скопировать подстроку этого класса при radix sort
l = 1
while l < n:
for i in xrange(n):
#при сортировке подстрок длины 2*l по 'младшим' вторым половинкам длины l - достаточно сместить уже сортированый массив на l
j = (sort_permutation[i] - l) % n
cl = group[j]
ptmp[group_start[cl]] = j #radix sort: то что отсортировано по вторым половинкам - теперь сортируем по первым 'старшим'
group_start[cl] += 1
sort_permutation, ptmp = ptmp, sort_permutation
new_class = -1
prev_cl = None
#проходим по подстрокам длины 2*l в порядке возрастания, для нумерации групп одинаковых строк
for i in xrange(n):
j = sort_permutation[i]
cl = (group[j], group[(j+l) % n])
if cl != prev_cl:
new_class += 1
group_start[new_class] = i
group_tmp[j] = new_class
prev_cl = cl
if new_class == n-1:
#все подстроки разные, можно не продолжать
break
group, group_tmp = group_tmp, group
l *= 2
return sort_permutation
def test():
def check_str(txt):
txt += '~' #last char - to avoid ambigous suffix sort
sa = suffix_sort(txt)
sa2 = trivial_suffix_sort(txt)
assert sa == sa2
import itertools
for k in xrange(10):
for t in itertools.product('abc', repeat=k):
txt = ''.join(t)
check_str(txt)
txt = 'three sweet switched swiss witches watch three washed swiss witch swatch watch switches. which sweet switched swiss witch watches which washed swiss witch swatch watch switch?'
check_str(txt)
for i in suffix_sort(txt):
print txt[i:min(len(txt), i + 30)]
if __name__ == "__main__":
test()
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.