Factor iterator in suffix tree of word

[sagetrac-evandomme]

We improve the algorithm computing the factor iterator in the implicit suffix tree of a word.

BEFORE:

sage: w = words.FibonacciWord([0,1])
sage: it = w[:10000].suffix_tree().factor_iterator()
sage: %time L = list(it)
Processus arrêté

AFTER:

sage: w = words.FibonacciWord([0,1])
sage: it = w[:10000].suffix_tree().factor_iterator()
sage: %time L = list(it)
CPU times: user 14 s, sys: 504 ms, total: 14.5 s
Wall time: 14.5 s
sage: len(L)
24337601

CC: @videlec @seblabbe

Component: combinatorics

Keywords: thursdaysbdx

Author: Vincent Delecroix, Élise Vandomme

Branch/Commit: d7bcfdf

Reviewer: Sébastien Labbé

Issue created by migration from https://trac.sagemath.org/ticket/25526

[sagetrac-evandomme]

Branch: u/evandomme/factor_iterator_in_suffix_tree_of_word

[seblabbe]

Commit: d7bcfdf

[seblabbe]

comment:2

Does the branch needs review?

---

New commits:

d7bcfdf

Better implmentation of the factor iterator in suffix tree of words

[seblabbe]

comment:3

Can you provide an example in the description of the ticket that shows how better the code has become with the improvement you propose?

[videlec]

comment:5

Replying to @seblabbe:

Can you provide an example in the description of the ticket that shows how better the code has become with the improvement you propose?

No. The reason is that there is no guarantee that iterating through a dictionary via iteritems you always get the same order (you can check that in the doctests there are sorted everywhere). But before this ticket, it was clearly not a DFS

sage: for w in Word("cacao").suffix_tree().factor_iterator(): print w
c
a
ac
aca
ao
acao
o
ca
cac
caca
cao
cacao

With this ticket it is

sage: for w in Word("cacao").suffix_tree().factor_iterator(): print w
a
ao
ac
aca
acao
o
c
ca
cao
cac
caca
cacao

[seblabbe]

comment:6

Replying to @videlec:

Replying to @seblabbe:

Can you provide an example in the description of the ticket that shows how better the code has become with the improvement you propose?

No.

I was asking in the description of the ticket not in a doctest.

[seblabbe]

comment:7

Before this ticket, this just eats all the memory and CPU:

sage: w = words.FibonacciWord([0,1])
sage: it = w[:10000].suffix_tree().factor_iterator()
sage: %time L = list(it)
Processus arrêté

With the branch of this ticket, I get:

sage: w = words.FibonacciWord([0,1])
sage: it = w[:10000].suffix_tree().factor_iterator()
sage: %time L = list(it)
CPU times: user 14 s, sys: 504 ms, total: 14.5 s
Wall time: 14.5 s
sage: len(L)
24337601

So, it is definitely an improvement.

[seblabbe]

Reviewer: Sébastien Labbé

[vbraun]

Changed branch from u/evandomme/factor_iterator_in_suffix_tree_of_word to d7bcfdf