context.trie(data="", format="default", filename="")

Generate a "trie" automaton (a prefix tree) from a finite series, given as a file of (weighted) words.

Arguments:

  • data: a string containing the list of words
  • format:
    • "default": same as "monomials"
    • "monomials": each line contains a weighted word in the monomials syntax: <2>foo
    • "words": each line contains a single word: foo. In this case <2>foo is read as a five-letter word.

Postconditions:

  • Result.is_deterministic()

See also:

Examples

Words (finite language)

In [1]:
import vcsn
vcsn.B.trie('''foo
bar
baz''')
Out[1]:
%3 I0 0 0 I0->0 F3 F6 F7 1 1 0->1 f 4 4 0->4 b 2 2 1->2 o 3 3 2->3 o 3->F3 5 5 4->5 a 6 6 5->6 r 7 7 5->7 z 6->F6 7->F7
In [2]:
%%file words
hello
world
hell
word
Overwriting words
In [3]:
vcsn.B.trie(filename='words')
Out[3]:
%3 I0 0 0 I0->0 F4 F5 F10 F11 1 1 0->1 h 6 6 0->6 w 2 2 1->2 e 3 3 2->3 l 4 4 3->4 l 4->F4 5 5 4->5 o 5->F5 7 7 6->7 o 8 8 7->8 r 9 9 8->9 l 11 11 8->11 d 10 10 9->10 d 10->F10 11->F11

Weighted words (finite series)

In [4]:
vcsn.Q.trie('''
one
<2>two
<3>three
<13>thirteen
<30>thirty
<51>thirsty''')
Out[4]:
%3 I0 0 0 I0->0 F3 F6 F10 F16 F17 F20 1 1 0->1 o 4 4 0->4 t 2 2 1->2 n 3 3 2->3 e 3->F3 5 5 4->5 w 7 7 4->7 h 6 6 5->6 o 6->F6 ⟨2⟩ 8 8 7->8 r 11 11 7->11 i 9 9 8->9 e 10 10 9->10 e 10->F10 ⟨3⟩ 12 12 11->12 r 13 13 12->13 t 18 18 12->18 s 14 14 13->14 e 17 17 13->17 y 15 15 14->15 e 16 16 15->16 n 16->F16 ⟨13⟩ 17->F17 ⟨30⟩ 19 19 18->19 t 20 20 19->20 y 20->F20 ⟨51⟩

Tuples of words

In [5]:
vcsn.context('lat<law_char, law_char>, q').trie('''
<1>one|un
<2>two|deux
<3>three|trois
<4>four|quatre
<14>forteen|quatorze
<40>forty|quarante''')
Out[5]:
%3 I0 0 0 I0->0 F3 F7 F12 F18 F24 F29 1 1 0->1 o|u 4 4 0->4 t|d 8 8 0->8 t|t 13 13 0->13 f|q 2 2 1->2 n|n 3 3 2->3 e|ε 3->F3 5 5 4->5 w|e 6 6 5->6 o|u 7 7 6->7 ε|x 7->F7 ⟨2⟩ 9 9 8->9 h|r 10 10 9->10 r|o 11 11 10->11 e|i 12 12 11->12 e|s 12->F12 ⟨3⟩ 14 14 13->14 o|u 15 15 14->15 u|a 19 19 14->19 r|a 16 16 15->16 r|t 17 17 16->17 ε|r 18 18 17->18 ε|e 18->F18 ⟨4⟩ 20 20 19->20 t|t 25 25 19->25 t|r 21 21 20->21 e|o 22 22 21->22 e|r 23 23 22->23 n|z 24 24 23->24 ε|e 24->F24 ⟨14⟩ 26 26 25->26 y|a 27 27 26->27 ε|n 28 28 27->28 ε|t 29 29 28->29 ε|e 29->F29 ⟨40⟩