comment générer un ensemble de chaînes similaires en python

Question

Je me demande comment générer un ensemble de chaînes similaires basées sur Levenshtein distance (chaîne d'édition de chaîne). Idéalement, j'aime transmettre, une chaîne source (c'est-à-dire une chaîne qui sert à générer d'autres chaînes similaires), le nombre de chaînes à générer et un seuil comme paramètres, c'est-à-dire des similarités entre les chaînes L'ensemble généré doit être supérieur au seuil. Je me demande quel (s) paquet (s) Python dois-je utiliser pour y parvenir? Ou n'importe quelle idée comment mettre en œuvre cela?

Answer 1

Je pense que vous pouvez penser au problème d'une autre manière (inversé).

• d'une chaîne, disent qu'il est Sittin.
• Étant donné un seuil (distance d'édition), disons k.
• Ensuite, vous appliquez des combinaisons de différentes "modifications" en k-étapes.

Par exemple, supposons que k = 2. Et supposons que le permis edit modes vous sont:

• supprimer un caractère
• ajouter un caractère
• remplacer un caractère par un autre.

Ensuite, la logique est quelque chose comme ci-dessous:

input = 'sittin' 
for num in 1 ... n: # suppose you want to have n strings generated 
    my_input_ = input 
    # suppose the edit distance should be smaller or equal to k; 
    # but greater or equal to one 
    for i in in 1 ... randint(k): 
    pick a random edit mode from (delete, add, substitute) 
    do it! and update my_input_ 

Si vous devez coller avec un dictionnaire prédéfini, qui ajoute une certaine complexité, mais il est encore faisable. Dans ce cas, la modification doit être valide.