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.

mots = ["abc", "abn", "aer", "bii", "bee", "bjk", "cap", "cbb"]
mots.sort()
mots

['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.

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)

2

Même fonction implémentée un peu différemment.

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)

{'c': 6, 'b': 3, 'a': 0}

On cherche maintenant les positions des mots commençant par un préfixe de deux lettres.

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)

{'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.

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

{'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é.

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)

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ù est la longueur de la liste triée. En utilisant la structure, on passe à un coût où est la longueur du préfixe et 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.

---

Notebook on github