Examples¶
Complete scripts, to copy and run as they are : each one prints what is shown below it. They are run by the
tests, so their outputs are up to date. Some use numpy (pip install numpy).
Validating identifiers¶
Strings are lists of code points : a set of characters is an IntervalSet, and the regular operations build the language of identifiers. Counting and uniform sampling come for free.
"""Text as code points : validate identifiers, count them, and draw random ones."""
import random
from autolib import Automaton, IntervalSet
# Symbols are integers : a string is the list of its code points
def codes(text):
return [ord(c) for c in text]
letter = IntervalSet([range(ord("a"), ord("z") + 1), range(ord("A"), ord("Z") + 1), ord("_")])
digit = IntervalSet(range(ord("0"), ord("9") + 1))
# [A-Za-z_][A-Za-z0-9_]* : a letter, then letters and digits
identifier = Automaton.symbols(letter) + Automaton.symbols(letter | digit).star()
for name in ["x", "_tmp1", "2fast", "snake_case", "kebab-case"]:
print(f"{name!r:14} {'valid' if codes(name) in identifier else 'invalid'}")
# How many identifiers of 8 characters ? 53 * 63**7, exactly
print("identifiers of 8 characters :", identifier.count_words(8))
# Random identifiers, uniformly among all of them
rng = random.Random(1)
print("random :", ["".join(map(chr, identifier.random_word(8, rng))) for _ in range(3)])
Output :
'x' valid
'_tmp1' valid
'2fast' invalid
'snake_case' valid
'kebab-case' invalid
identifiers of 8 characters : 208765973875851
random : ['nfUl0wAl', 'EW6LdO0e', 'IQoF4KEC']
Suspicious sequences in event logs¶
Events are small integers, and a log is a numpy array of a million of them. A Searcher finds every brute-force login in one pass, without copying the array.
"""Event logs : find suspicious sequences in a long numpy array of events."""
import numpy as np
from autolib import Automaton
LOGIN_OK, LOGIN_FAILED, READ, WRITE, LOGOUT = range(5)
# Three failed logins or more, then a success : a brute force that worked
suspicious = Automaton(f"<{LOGIN_FAILED}>{{3,}}<{LOGIN_OK}>").searcher()
rng = np.random.default_rng(42)
log = rng.choice(5, size=1_000_000, p=[0.2, 0.25, 0.3, 0.2, 0.05]).astype(np.int32)
matches = suspicious.find_all(log) # one pass over the million events
print("suspicious sequences :", len(matches))
first = matches[0]
print("first one at", first.start, ":", log[first.start:first.end].tolist())
print("longest :", max(len(m) for m in matches), "events")
Output :
suspicious sequences : 3050
first one at 371 : [1, 1, 1, 0]
longest : 9 events
DNA motifs on both strands¶
A motif with alternatives, and its reverse complement on the other strand : the union of both automata searches both at once.
"""DNA motifs : search a pattern and its reverse complement in a random genome."""
import numpy as np
from autolib import Automaton
A, C, G, T = range(4)
complement = {A: T, C: G, G: C, T: A}
# TATA box : TATA, then A or T, then A, then A or T
motif = [T, A, T, A, (A, T), A, (A, T)]
def expression(pattern):
parts = []
for base in pattern:
options = base if isinstance(base, tuple) else (base,)
parts.append("(" + "|".join(str(b) for b in options) + ")")
return "".join(parts)
forward = Automaton(expression(motif))
# The other strand reads the complement, backwards
backward = Automaton(expression([tuple(complement[b] for b in x) if isinstance(x, tuple) else complement[x]
for x in reversed(motif)]))
both = forward | backward
genome = np.random.default_rng(3).integers(0, 4, 2_000_000, dtype=np.int32)
print("words of the motif :", forward.count_words(7))
print("on the forward strand :", len(forward.searcher().find_all(genome)))
print("on either strand :", len(both.searcher().find_all(genome)))
Output :
words of the motif : 4
on the forward strand : 506
on either strand : 873
Counting and drawing words¶
Exact counts with Python integers, the words of a length in order, ranks, and uniform draws among balanced parentheses.
"""Combinatorics on words : counts, ranks and uniform draws, exactly."""
import random
from autolib import Automaton, WordSampler
no_11 = Automaton("~(.*11.*)&(0|1)*") # binary words without two consecutive 1
print("counts :", [no_11.count_words(n) for n in range(12)]) # Fibonacci numbers
print("length 500 :", no_11.count_words(500))
# All the words of length 4, in lexicographic order, then by rank
print("length 4 :", ["".join(map(str, w)) for w in no_11.words(4) if len(w) == 4])
sampler = WordSampler(no_11, 4)
print("rank of 0101 :", sampler.rank([0, 1, 0, 1]), "- word of rank 5 :", sampler[5])
# Balanced parentheses up to a depth : 0 opens, 1 closes
depth_3 = Automaton("(0(0(01)*1)*1)*")
print("balanced, depth 3, length 10 :", depth_3.count_words(10))
print("one at random :", "".join("()"[c] for c in depth_3.random_word(10, random.Random(5))))
Output :
counts : [1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233]
length 500 : 365014740723634211012237077906479355996081581501455497852747829366800199361550174096573645929019489792751
length 4 : ['0000', '0001', '0010', '0100', '0101', '1000', '1001', '1010']
rank of 0101 : 4 - word of rank 5 : [1, 0, 0, 0]
balanced, depth 3, length 10 : 34
one at random : (())((()))
Spelling suggestions with edit distances¶
A weighted automaton whose cost is the edit distance to a word : insertions and substitutions read any letter, deletions are epsilon transitions. k_best_words lists the closest words, cheapest first.
"""Spelling suggestions : an edit-distance automaton, and the cheapest words it accepts."""
from autolib import IntervalSet, WeightedAutomaton
ALPHABET = IntervalSet(range(ord("a"), ord("z") + 1))
def within_edits(target, max_edits):
"""Words within max_edits edits of target; the cost of a word is its edit distance."""
b = WeightedAutomaton.Builder()
n = len(target)
# State (i, e) : i letters of the target read, e edits made
state = {(i, e): b.add_state() for i in range(n + 1) for e in range(max_edits + 1)}
b.set_initial(state[0, 0])
for (i, e), s in state.items():
if i == n:
b.set_accept(s)
if i < n:
b.add_transition(s, state[i + 1, e], ord(target[i]), 0.0) # match
if e < max_edits:
b.add_transition(s, state[i, e + 1], ALPHABET, 1.0) # insertion
if i < n:
b.add_transition(s, state[i + 1, e + 1], ALPHABET, 1.0) # substitution
b.add_epsilon(s, state[i + 1, e + 1], 1.0) # deletion
return b.build()
dictionary = ["cat", "cart", "chat", "coat", "dog", "act", "cast", "scat", "at", "car"]
typos = within_edits("cat", 1)
for word in dictionary:
cost = typos([ord(c) for c in word])
print(f"{word:5} {'distance ' + str(int(cost)) if cost < float('inf') else 'too far'}")
# The closest words, cheapest first : no dictionary needed
closest = typos.k_best_words(4)
print("closest :", [("".join(map(chr, w.symbols)), w.cost) for w in closest])
Output :
cat distance 0
cart distance 1
chat distance 1
coat distance 1
dog too far
act too far
cast distance 1
scat distance 1
at distance 1
car distance 1
closest : [('cat', 0.0), ('ca', 1.0), ('ct', 1.0), ('at', 1.0)]
Journeys : time against money¶
Two costs per leg of a journey. The Pareto front keeps the journeys that no other beats on both costs; a price of time chooses one.
"""Journeys with two costs, time and money : the Pareto front and the price of time."""
from autolib import MultiWeightedAutomaton
TIME, MONEY = 0, 1
legs = { # (from, to) : options (name, minutes, euros)
("home", "station"): [("walk", 15, 0), ("bus", 8, 2), ("taxi", 5, 9)],
("station", "airport"): [("train", 40, 6), ("express", 20, 18)],
("home", "airport"): [("taxi", 45, 55), ("shuttle", 70, 12)],
}
b = MultiWeightedAutomaton.Builder(2)
place = {p: b.add_state() for p in ["home", "station", "airport"]}
b.set_initial(place["home"])
b.set_accept(place["airport"])
names = {}
for (a, z), options in legs.items():
for name, minutes, euros in options:
names[b.add_transition(place[a], place[z], 0, [minutes, euros])] = name
journeys = b.build()
print("Pareto front :")
for path in sorted(journeys.pareto_front(), key=lambda p: p.costs):
print(f" {int(path.cost(TIME)):3} min {int(path.cost(MONEY)):3} EUR {' + '.join(names[e] for e in path.edges)}")
for euros_per_hour in [5, 20, 60]:
best = journeys.scalarize([euros_per_hour / 60, 1]).best_path()
print(f"time worth {euros_per_hour:2} EUR/h : {' + '.join(names[e] for e in best.edges)}")
Output :
Pareto front :
25 min 27 EUR taxi + express
28 min 20 EUR bus + express
35 min 18 EUR walk + express
45 min 15 EUR taxi + train
48 min 8 EUR bus + train
55 min 6 EUR walk + train
time worth 5 EUR/h : walk + train
time worth 20 EUR/h : bus + train
time worth 60 EUR/h : bus + express
Scheduling with hourly prices¶
The rules of a schedule are an automaton : six hours a day, by blocks of at least two. An unfolding by hour gives each hour its price, and the best path is the cheapest schedule.
"""Scheduling with prices that change by the hour : costs depending on the position."""
from autolib import Automaton, LayeredAutomaton
OFF, ON = 0, 1
# Cents per kWh, hour by hour : cheap at night and at midday, when the sun shines
price = [24, 18, 17, 19, 26, 31, 38, 45, 42, 33, 25, 19, 15, 14, 16, 22, 34, 47, 52, 49, 40, 33, 28, 26]
# A machine runs 6 hours a day, by blocks of at least 2 hours
blocks = Automaton("0*(11+0+)*(11+)?")
six_hours = Automaton("0*(10*){6}")
rules = blocks & six_hours
plan = rules.snapshot().weighted(lambda edge: 1.0 if ON in edge.labels else 0.0)
layers = LayeredAutomaton.exactly(plan.graph, 24)
analysis = layers.analyze(plan, lambda hour, edge: price[hour] * plan.weight(edge))
best = analysis.best_path()
print("cost :", analysis.optimal_cost)
print("hours on :", [hour for hour, s in enumerate(best.symbols) if s == ON])
print("schedule :", "".join("#" if s == ON else "." for s in best.symbols))
Output :
cost : 99.0
hours on : [1, 2, 3, 12, 13, 14]
schedule : .###........###.........