Recherche de préfixes¶
On dispose d’une liste triée de mots. Un très grande liste. On cherche à connaître la position du premier de cette liste commençait par un certain préfixe.
[4]:
mots = ["abc", "abn", "aer", "bii", "bee", "bjk", "cap", "cbb"]
mots.sort()
mots
[4]:
['abc', 'abn', 'aer', 'bee', 'bii', 'bjk', 'cap', 'cbb']
On cherche les position des premiers mot de la liste triée commençant par chaque lettre.
[5]:
def position_premiere_lettre(prefixe, mots):
# retourne position du premier commençant par le préfixe prefixe
for i, mot in enumerate(mots):
if mot.startswith(prefixe):
return i
return -1
position_premiere_lettre("ae", mots)
[5]:
2
Même fonction implémentée un peu différemment.
[6]:
def position_premiere_lettre(mots):
p = {}
for i in range(len(mots) - 1, -1, -1):
p[mots[i][0]] = i
return p
position_premiere_lettre(mots)
[6]:
{'c': 6, 'b': 3, 'a': 0}
On cherche maintenant les positions des mots commençant par un préfixe de deux lettres.
[7]:
def position_lettre(mots, a=0, b=None, pos=0):
p = {}
if b is None:
b = len(mots)
for i in range(b - 1, a - 1, -1):
p[mots[i][pos]] = i
return p
def position_deux_lettres(mots):
pos1 = position_premiere_lettre(mots)
elements = list(sorted(pos1.items()))
pos2 = {}
for i, (c, p) in enumerate(elements):
if i < len(elements) - 1:
pos2[c] = position_lettre(mots, p, elements[i + 1][1], pos=1)
else:
pos2[c] = position_lettre(mots, p, pos=1)
return pos2
position_deux_lettres(mots)
[7]:
{'a': {'e': 2, 'b': 0}, 'b': {'j': 5, 'i': 4, 'e': 3}, 'c': {'b': 7, 'a': 6}}
Peut-on adapter cette fonction à toute longueur de préfixe ? L’idée est de construire le résultat de façon récursive.
[8]:
def build_dictionary(mots, increment=0):
premiere_lettre = {}
for i, mot in enumerate(mots):
if len(mot) == 0:
continue
initial = mot[0]
if initial not in premiere_lettre:
premiere_lettre[initial] = i
dico = {}
for initial, position1 in premiere_lettre.items():
position_lettre_apres = [i for i in premiere_lettre.values() if i > position1]
position2 = (
len(mots) if len(position_lettre_apres) == 0 else min(position_lettre_apres)
)
sous_mots = mots[position1:position2]
if len(sous_mots) == 0:
dico[initial] = (position1 + increment, None)
else:
sous_mots_1 = [m[1:] for m in sous_mots]
sous_dico = build_dictionary(sous_mots_1, position1 + increment)
dico[initial] = (position1 + increment, sous_dico)
return dico
dico = build_dictionary(mots)
dico
[8]:
{'a': (0, {'b': (0, {'c': (0, {}), 'n': (1, {})}), 'e': (2, {'r': (2, {})})}),
'b': (3,
{'e': (3, {'e': (3, {})}),
'i': (4, {'i': (4, {})}),
'j': (5, {'k': (5, {})})}),
'c': (6, {'a': (6, {'p': (6, {})}), 'b': (7, {'b': (7, {})})})}
Ensuite on peut utiliser cette structure pour accélérer la recherche du premier mots d’une liste triée commençant par un préfixe donné.
[9]:
def position_prefixe_dico(prefixe, dico):
d = dico
pos = 0
for c in prefixe:
pos = d[c][0]
d = d[c][1]
return pos
position_prefixe_dico("be", dico)
[9]:
3
Comme souvent, la structure permet un gain de temps lors de la recherche. La recherche dichotomique dans une liste triée à un coût en \(O(\log_2 N)\) où \(N\) est la longueur de la liste triée. En utilisant la structure, on passe à un coût \(O(L\log_2 C)\) où \(L\) est la longueur du préfixe et \(C\) le nombre de caractères, en général 26 pour une langue latine. La structure est toujours avantageuse lorsque la liste est grande car l’alphabet est petit et ne peut croître, la longueur du préfixe est elle aussi petite.
[ ]: