Python - différence entre deux chaînes de caractères

Question

J'aimerais stocker un grand nombre de mots dans une liste. Beaucoup de ces mots sont très similaires. Par exemple, j'ai le mot afrykanerskojezyczny et de nombreux mots comme afrykanerskojezycznym , afrykanerskojezyczni , nieafrykanerskojezyczni . Quelle est la solution efficace (rapide et donnant une petite taille de diff) pour trouver la différence entre deux chaînes de caractères et restaurer la seconde chaîne à partir de la première et de la diff ?

Answer 1

Vous pouvez utiliser ndiff dans le module difflib pour faire cela. Il contient toutes les informations nécessaires pour convertir une chaîne de caractères en une autre chaîne de caractères.

Un exemple simple :

import difflib

cases=[('afrykanerskojezyczny', 'afrykanerskojezycznym'),
       ('afrykanerskojezyczni', 'nieafrykanerskojezyczni'),
       ('afrykanerskojezycznym', 'afrykanerskojezyczny'),
       ('nieafrykanerskojezyczni', 'afrykanerskojezyczni'),
       ('nieafrynerskojezyczni', 'afrykanerskojzyczni'),
       ('abcdefg','xac')] 

for a,b in cases:     
    print('{} => {}'.format(a,b))  
    for i,s in enumerate(difflib.ndiff(a, b)):
        if s[0]==' ': continue
        elif s[0]=='-':
            print(u'Delete "{}" from position {}'.format(s[-1],i))
        elif s[0]=='+':
            print(u'Add "{}" to position {}'.format(s[-1],i))    
    print()      

des empreintes :

afrykanerskojezyczny => afrykanerskojezycznym
Add "m" to position 20

afrykanerskojezyczni => nieafrykanerskojezyczni
Add "n" to position 0
Add "i" to position 1
Add "e" to position 2

afrykanerskojezycznym => afrykanerskojezyczny
Delete "m" from position 20

nieafrykanerskojezyczni => afrykanerskojezyczni
Delete "n" from position 0
Delete "i" from position 1
Delete "e" from position 2

nieafrynerskojezyczni => afrykanerskojzyczni
Delete "n" from position 0
Delete "i" from position 1
Delete "e" from position 2
Add "k" to position 7
Add "a" to position 8
Delete "e" from position 16

abcdefg => xac
Add "x" to position 0
Delete "b" from position 2
Delete "d" from position 4
Delete "e" from position 5
Delete "f" from position 6
Delete "g" from position 7

Answer 2

J'aime la réponse ndiff, mais si vous voulez tout cracher dans une liste de seulement les changements, vous pourriez faire quelque chose comme :

import difflib

case_a = 'afrykbnerskojezyczny'
case_b = 'afrykanerskojezycznym'

output_list = [li for li in difflib.ndiff(case_a, case_b) if li[0] != ' ']

Answer 3

Vous pouvez consulter le module regex (la section floue). Je ne sais pas si vous pouvez obtenir les différences réelles, mais au moins vous pouvez spécifier le nombre autorisé de différents types de changements comme l'insertion, la suppression et les substitutions :

import regex
sequence = 'afrykanerskojezyczny'
queries = [ 'afrykanerskojezycznym', 'afrykanerskojezyczni', 
            'nieafrykanerskojezyczni' ]
for q in queries:
    m = regex.search(r'(%s){e<=2}'%q, sequence)
    print 'match' if m else 'nomatch'

Answer 4

Ce que vous demandez est une forme spécialisée de compression. xdelta3 a été conçu pour ce type particulier de compression, et il existe une liaison python pour lui, mais vous pouvez probablement vous en sortir en utilisant directement zlib. Vous pouvez utiliser zlib.compressobj y zlib.decompressobj avec le zdict réglé sur votre "mot de base", par exemple. afrykanerskojezyczny .

Les mises en garde sont zdict n'est supporté qu'à partir de la version 3.3 de python, et il est plus facile à coder si vous avez le même "mot de base" pour tous vos diffs, ce qui n'est pas forcément ce que vous voulez.

Answer 5

Vous trouverez peut-être les outils disponibles dans le NLTK bibliothèque utile pour calculer la différence entre différents mots.

nltk.metrics.distance.edit_distance() est une implémentation mature (non standard) de la bibliothèque qui calcule l'indice distance de Levenshtein

Un exemple simple pourrait être :

from nltk.metrics.distance import *

w1 = 'wordone'
w2 = 'wordtwo'
edit_distance(w1, w2)

Out: 3

Des paramètres supplémentaires permettent de pondérer la sortie, en fonction des coûts des différentes actions (substitutions/insertions) et des différences entre les caractères (par exemple, un coût moindre pour les caractères les plus proches du clavier).