Vous êtes coincé aussi loin que Big-O est concerné. À un niveau fondamental, vous devrez tester si chaque lettre de la cible correspond à chaque lettre admissible dans la sous-chaîne.

Heureusement, cela est facilement parallélisé.

Une optimisation que vous pouvez appliquer est de conserver un nombre de décomptes de fonctionnement de la position actuelle. Si c'est plus grand que la distance de frappe la plus basse jusqu'à présent, vous pouvez évidemment passer à la prochaine possibilité.

MODIFIÉ BOYER-MOORE

Je viens de creuser une vieille implémentation de python de BOYER-MOORE J'avais couché et j'ai modifié la boucle correspondante (où le texte est comparé au motif). Au lieu de briser dès que la première inadéquation se trouve entre les deux cordes, comptez simplement le nombre de désactivités, mais N'oubliez pas la première désactivation forte>: p> xxx pré>

Si la chaîne ne correspondait pas complètement à ce stade, revenez au point de la première inadéquation en restaurant les valeurs. Cela garantit que la plus petite distance est réellement trouvée. P>

Toute la mise en œuvre est plutôt longue (~ 150LOC), mais je peux le poster sur demande. L'idée principale est décrite ci-dessus, tout le reste est standard Boyer-Moore. P>

Prétraitement sur le texte H1>

Un autre moyen de faire accélérer les choses est la prétraitement du texte pour avoir un index sur les positions de caractère . Vous ne voulez que commencer à comparer à des positions où au moins une seule correspondance entre les deux chaînes se produit, sinon la distance de Hamming est | S | trivialement. p> xxx pré>

Cette méthode crée simplement un dictionnaire qui mappe chaque caractère dans le texte à la liste triée de ses occurrences. P>

La boucle de comparaison est plus ou moins Inchangé à naïf O (mn) code> Approche, à part le fait que nous n'augmentons pas la position à laquelle la comparaison est démarrée par 1 chaque fois, mais sur la base des positions de caractère: P>

def find_next_pos(pattern, pos, i):
    smallest = sys.maxint
    for idx, c in enumerate(pattern):
        if c in pos:
            x = bisect.bisect_left(pos[c], i + idx)
            if x < len(pos[c]):
                smallest = min(smallest, pos[c][x] - idx)
    return smallest

Peut-être surprenant, ce problème exact peut être résolu en juste O (| A | Nlog n) Heure à l'aide de FFTS Fourier Transforms (FFTS), où n est la longueur de la plus grande séquence L et | a | est la taille de l'alphabet.

Voici un fichier PDF librement disponible d'un document de Donald Benson décrivant comment cela fonctionne:

• Méthodes de Fourier pour l'analyse de la biosequence (Donald Benson, < EM> Recherche d'acides nucléiques 1990 Vol. 18, p. 3001-3006)

  Résumé: Convertissez chacune de vos chaînes S et l dans plusieurs vecteurs (un par caractère, donc 4 dans le cas de l'ADN), puis Convolvez Vecteurs correspondants pour déterminer les chiffres de correspondance pour chaque possible alignement. L'astuce est que la convolution dans le domaine "temps", qui nécessite habituellement une heure O (n ^ 2), peut être mise en œuvre à l'aide de la multiplication dans le domaine "fréquence", qui nécessite juste O (n) temps, plus le temps nécessaire pour convertir entre les domaines et le dos à nouveau. L'utilisation de la FFT Chaque conversion prend juste une heure (Nlog N), de sorte que la complexité du temps global est O (| A | Nlog N). Pour une vitesse la plus grande, les champs finis sont utilisés, ce qui nécessite uniquement des arithmétiques entier.

  Remarque: pour arbitraire S et l Cet algorithme est clairement une énorme victoire de performances sur l'algorithme de O (mn). > | S | et | l | devient grand, mais otoh si s est généralement plus court que log | l | (par exemple Lors de la requête d'une grande dB avec une petite séquence), alors évidemment cette approche ne fournit aucune vitesse.

  update 21/7/2009 : mis à jour pour mentionner que la complexité temporelle dépend également de manière linéaire de la taille de l'alphabet, car une paire de vecteurs indicateurs distinct doit être utilisée pour chaque caractère de l'alphabet .