DFA that tracks phrases of power

[Vlad-Shcherbina]

It consumes characters one by one, and after each character increments some of 18 counters, each corresponding to number of occurrences of individual power phrases.

I expect this automaton to have not too many states (less than twice the total length of all power words).

I think it'll be very useful for dynamic programming approximations to the solution.

[mdragus]

I will be working on this.

[mdragus]

This is submitted. There is a stress test and a few normal tests. The only possible issue is the fact that currently if the word is "aa" and the text is "aaaaaa" we get a total of 3 matches, not 5 (which we don't know if it is correct.)

[mdragus]

FullDfa is the only

Usage:

from production.dfa import FullDfa
x = FullDfa(["aa","aaaa"], ['a','b'])
x.get_final_state_lookup()
{frozenset({'aaaa_3_a', 'aa_2_a'}): ['aa'], frozenset({'aa_2_a', 'aaaa_2_a'}): ['aa'], frozenset({'aaaa_4_a', 'aa_2_a'}): ['aa', 'aaaa']}
x.get_dfa()
{frozenset({'aaaa_3_a', 'aa_2_a'}): {'b': frozenset({'start'}), 'a': frozenset({'aaaa_4_a', 'aa_2_a'})}, frozenset({'aa_1_a', 'aaaa_1_a'}): {'b': frozenset({'start'}), 'a': frozenset({'aa_2_a', 'aaaa_2_a'})}, frozenset({'aa_2_a', 'aaaa_2_a'}): {'b': frozenset({'start'}), 'a': frozenset({'aaaa_3_a', 'aa_2_a'})}, frozenset({'start'}): {'b': frozenset({'start'}), 'a': frozenset({'aa_1_a', 'aaaa_1_a'})}, frozenset({'aaaa_4_a', 'aa_2_a'}): {'b': frozenset({'start'}), 'a': frozenset({'aaaa_4_a', 'aa_2_a'})}}
x.add_letter('a')
x.add_letter('a')
x.add_letter('a')
x.add_letter('a')
x.add_letter('a')
x.get_scores()
['aa', 'aa', 'aa', 'aaaa', 'aa', 'aaaa', 'aa', 'aaaa']

[peluche]

working on adding hypothesis tests

[peluche]

Tests added and passing

I changed the API a bit,

• previously .get_scores() returned a list of all the matches in order of matching.
• now it only return a dict of {match: number_of_matches} to prevent wasting memory