Méthode efficace pour comparer deux chaînes (l'ordre des caractères non pertinent)

Question

J'essaie de trouver un algorithme pour comparer deux chaînes. Il enregistrerait une correspondance avec les mots contenant les mêmes lettres. Par exemple, rent et stern seraient équivalents, car ils contiennent tous deux les lettres r, e, n, t.

MODIFIER Je m'excuse d'être si vague. La comparaison sera faite sur deux séries de quelques milliers de mots des centaines de fois. Ceci n’est qu’une petite partie du code général, je ne veux donc pas tout gâcher.

Pour ceux qui demandaient oui, il serait très important que la correspondance des chiffres soit la même, par exemple le loyer correspondrait au ternic

MODIFIER 2 Pour un match comme rent == ternicate, ternicate ne correspond pas au loyer. C'est plus comme si le mot deux contient les lettres du mot un. Donc, si vous avez des lettres en plus, cela correspond quand même tant que le mot contient toutes les lettres du premier mot.

Answer 1

D'accord, c'est une très mauvaise idée, mais c'est tellement fou que ça pourrait marcher!

1. Créez une liste des 26 premiers nombres premiers.

   primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, ...]
   

2. Pour chaque lettre d'un mot, trouvez le nombre premier correspondant. A & # 8594; 2, B & # 8594; 3, C & # 8594; 5, etc.

3. Multipliez ces nombres premiers ensemble. Vous allez vous retrouver avec un (très grand) nombre.

Les mots qui ont les mêmes lettres auront le même numéro. Les mots avec des lettres différentes sont garantis d'avoir des nombres différents. Pourquoi est-ce?

Comme nous multiplions les nombres premiers, nous obtiendrons toujours des produits uniques pour des combinaisons uniques de lettres. Les nombres peuvent être décomposés en leurs facteurs premiers et les facteurs nous indiquent précisément quelles lettres étaient dans le mot original. L'ordre des lettres n'est pas conservé, mais quelles lettres étaient dans le mot et combien il y en avait.

Par exemple, prenez les mots & "; face &"; et & "café &";

FACE = 13 * 2 * 5 * 11 = 1430  
CAFE = 5 * 2 * 13 * 11 = 1430

Ha! Quoi de plus efficace qu'une simple comparaison d'entiers?

...

D'accord, non, peut-être pas. Ceci est un peu trop ridicule pour réellement utiliser. C'est chouette cependant.

Answer 2

Triez simplement les caractères de chaque chaîne, puis comparez-les.

rent == tern
enrt == enrt

Answer 3

La clé ici, étant donné l’ambiguïté de la question, c’est que il ne semble pas qu'il soit nécessaire de compter le nombre de fois qu'une lettre apparaît, mais seulement .

Par conséquent, en supposant que toutes les lettres sont dans la plage a-z, et en supposant qu'il est possible d'indexer les listes de mots d'origine sous forme de tableaux à l'aide d'indices entiers:

1. crée deux tableaux (un pour chaque liste).

2. pour chaque mot des deux listes, calcule l'image bitmap comme suit:

bitmap = 0
foreach (character in word) {
    bitmap |= (1 << (character - 'a'))
}
arrayX[index] = bitmap;

ce bitmap représente l’ensemble des lettres qui apparaissent dans ce mot.

3. puis pour chaque mot de l'ensemble A, effectuez une itération sur l'ensemble B et correspondez lorsque

arrayA[indexA] | arrayB[indexB] == arrayB[indexB]

Ce test ne sera vrai que si l'ensemble des caractères de ce mot A est un sous-ensemble des caractères du mot B. Les & "; ou &"; opération pour les bits est l'équivalent de l'opérateur d'union (& # 8746;) pour les ensembles réels.

Voir l'entrée Wikipedia sur définir mathemtatics - A & # 8838; B si et seulement si A & # 8746; B = B.

BTW, l’étape 3 correspond à O (n ^ 2), mais doit rester très rapide car c’est une comparaison bit à bit. Quelques milliers de mots dans chaque liste (~ 4 millions de tests) devraient prendre moins d’une seconde.

Answer 4

Une alternative consiste à compter le nombre de chaque caractère dans chaque chaîne et à comparer les nombres. Une implémentation simple devrait prendre O(max(N, A)) un temps où N est la longueur de la plus grande des chaînes et A la taille du tableau que vous utilisez pour stocker les comptes. Par exemple, en Java:

public boolean equalIgnoringOrder(String s1, String s2) {
    if (s1.length() != s2.length()) {
        return false;
    }
    // Assuming characters in the range ASCII 0 to 127 
    int[] c1 = new int[128];
    int[] c2 = new int[128];
    for (int i = 0; i < s1.length(); i++) {
        c1[s1.charAt(i)]++;
        c2[s2.charAt(i)]++;
    }
    for (int i = 0; i < c1.length; i++) {
        if (c1[i] != c2[i]) {
            return false;
        }
    }
    return true;
}

Il y a quelques améliorations possibles à cela. Par exemple, vous pouvez gérer un jeu de caractères arbitraire en réduisant les plages. c’est-à-dire que vous effectuez un premier passage dans s1 et s2 en recherchant les caractères les plus petits et les plus grands dans chacun d’eux, et vous en servent pour déterminer la taille de c1 et c2 et un décalage de base. Cela utilisera moins d'espace en moyenne et réduira le temps nécessaire pour initialiser les tableaux de comptage. Il offre également un court-circuit pour la comparaison; par exemple. lorsque les caractères les plus petits et les plus grands pour O(NlogN) et O(N) ne sont pas identiques.

Par comparaison, comparer les chaînes triées à l'aide de tas ou quicksort serait O(N*N) en moyenne avec equals espace, N étant la plus grande longueur de la chaîne.

Cependant, comme le souligne @pst, les constantes de proportionnalité peuvent rendre un algorithme 2 * N ou même <=> meilleur qu'un algorithme <=> si N n'est pas grand. Dans ce cas, la longueur moyenne des chaînes comparées est probablement le facteur le plus important.

Le code ci-dessus effectue effectivement un tri de base avec quelques courts-circuits. (Trois si vous incluez le court-circuit associé à la réduction de la plage.) En définitive, cela revient donc à déterminer si un tri rapide / tri de tas ou un tri de base serait préférable. Et cela dépend de la longueur de la chaîne d'entrée et de la plage de caractères.

Sur un autre plan. La réponse de @ John propose de calculer un produit de nombres premiers. Si nous faisons le calcul en utilisant une représentation de précision arbitraire, les valeurs résultantes seront uniques pour chaque ensemble distinct de & Quot; ordre d'ignorance égal & Quot; des cordes. Malheureusement, le calcul sera <=>. (Chaque produit intermédiaire a <=> chiffres et multiplier un nombre à N chiffres par une constante est <=>. Faites cela pour N caractères et vous obtenez <=>.)

Mais si nous faisons le calcul modulo (par exemple) 64, le résultat est en réalité un très bon hash insensible à l’ordre des caractères; par exemple

long hash = 1;
for (int i = 0; i < s.length(); i++) {
    hash = hash * primes[s.charAt(i)];
}

Donc, je dirais que l'algorithme qui offre les meilleures performances et la meilleure utilisation de l'espace en moyenne pour comparer des chaînes générées aléatoirement est probablement de la forme:

if (s1.length() != s2.length()) {
    return false;
}
if (hash(s1) != hash(s2)) { // computed as above
    return false;
}
// Compare using sorting or character counting as above.

Un dernier point. Si nous supposons que les pointeurs de chaîne ne sont pas identiques et que les chaînes ont des longueurs inégales, tout algorithme qui calcule ce <=> prédicat doit être à <=> ou pire. Il doit examiner chaque caractère des deux chaînes pour prendre cette décision, ce qui nécessite <=> opérations.

Tout algorithme effectuant moins de <=> lectures ou moins de <=> opérations sur les valeurs extraites dans ce scénario est manifestement incorrect.

Answer 5

Je suis d'accord avec Stephen C - ce n'est pas assez bien défini pour répondre .

Je ne voterai pas, mais pourriez-vous expliquer, par exemple, si le loyer équivaut à un loyer? Vous avez des répondants qui supposent que c'est le cas (ceux qui pensent que le nombre d'occurrences importe peu) et les autres qui assument le pire. Un de ces groupes perd son temps.

De plus, puisque votre préoccupation concerne les performances, nous devons en savoir plus sur votre structure d’appel. Pouvez-vous expliquer si vous allez regarder une paire d'ensembles plus d'une fois ou si les ensembles varient?

Et, à titre de terminologie terminale, vous le savez peut-être déjà, mais avec la formulation actuelle, votre algorithme n'est pas symétrique.

Vous dites que le loyer correspondrait à un ternicier, mais que, évidemment, ce ternicier ne correspondrait pas à un loyer. Donc, vous ne recherchez pas vraiment l'équivalence. Vous recherchez quelque chose comme & "se trouve dans &"; ou & "peut être fabriqué à partir de quot ;.

Cela signifie que vous devez vous soucier de l'ordre - vous obtiendrez des résultats différents selon la façon dont vous visitez vos ensembles.

Ne vous méprenez pas: c'est un problème intéressant ... Je ne sais pas quel est le problème.

Answer 6

peut-être pas le fastet, mais probablement la solution la plus courte utilisant java + google-collections + goyave (pour la diffusion char[] - > List<Character>)

import com.google.common.collect.ImmutableMultiset;
import com.google.common.primitives.Chars;

public class EqualsOrderignore {
private static boolean compareIgnoreOrder(final String s1, String s2) {
    return ImmutableMultiset.copyOf(Chars.asList(s1.toCharArray()))
            .equals(ImmutableMultiset.copyOf(Chars.asList(s2.toCharArray())));
} 
}

exécution de cet algorithme: O (s1.length + s2.length)

Je suis convaincu que cette solution fonctionnera comme une solution O (N1 + N2) fabriquée à la main sur une machine virtuelle serveur.

En plus, cette solution fonctionnera pour toutes les occurrences de caractères, pas seulement pour a-Z.

Answer 7

J'ai écrit beaucoup de code qui fonctionne avec les jeux de mots et les anagrammes. L'approche habituelle consiste à convertir le mot en une clé triée de sorte que, comme mentionné ci-dessus, "rent" corresponde à "stern" car les deux mappent vers "enrt". Une fois que vous avez commencé sur cette route, cependant, il devient vraiment utile d’avoir un dictionnaire de caractères et un nombre d’occurrences. Voici un code python qui convertit une chaîne non triée en dictionnaire avec (clé = caractère, valeur = nombre):

import collections

# Create a defaultdict(int) from a string
def create_collections_dict(key):
    dk = collections.defaultdict(int)
    for k in key:
        dk[k] += 1
    return dk

Vous pouvez maintenant marquer des mots contre d'autres en remarquant instantanément le nombre de lettres qu'ils ont en commun:

# Score the similarity of a defaultdict(int) against a string
# (which is temporarily converted to a defaultdict(int))
def score(dk, cand) :
    dc = create_collections_dict(cand)
    return sum(min(dk[k], dc[k]) for k in dk.keys() if k in dc)

if __name__ == '__main__':
    base = create_collections_dict('rent')
    for word in ['tern', 'ternicate', 'foobar']:
        print word, score(base, word)

Résultats:

tern 4
ternicate 4
foobar 1

Answer 8

En supposant que:

1. vos mots sont uniquement composés de caractères ascii
2. la casse n'a pas d'importance
3. abc correspond à abcde et abcde ne correspond pas à abc

Vous pouvez parcourir la chaîne de correspondance (s2) en comptant les caractères, puis la valeur (s1) et vérifier que tous les caractères sont présents dans l'autre, quelque chose comme (pseudo-code, non coché):

boolean matches(String s1, String s2) {
   int[]  counts = new int[256];
   char[] c1;
   char[] c2;

   c1 = s1.getCharArray();
   c2 = c2.getCharArray();

   // count char occurences in longest string
   for (int n = 0; n < c2.length; n++) {
       counts[(int)c2[n]]++;
   }

   // check all chars in shortest string are foud in the longest
   for (int n = 0; n < c1.length; n++) {
       if (0 == counts[(int)c1[n]]) {
          return false;
       }
   }

   return true;
}

Ce serait O (n) pour la somme des longueurs d'argument.

Éditer: la question a été remplacée par une fonction asymétrique entre s1 et s2.

Answer 9

C'est assez vague, mais j'utiliserais un tableau associatif pour le résoudre:

Utilisez chaque lettre de chaque mot comme clé d’un tableau associatif d’entiers. Les lettres d'un mot incrémentent les valeurs et l'autre décrémente. Ensuite, à la fin, vous pouvez parcourir toutes les clés et vérifier que toutes les valeurs sont égales à zéro. Cela vous donne une fonctionnalité de base == à louer.

Mises en garde concernant l'imprécision: 1. Si plusieurs lettres vous conviennent, par exemple rent == rreenntt, lors de l'ajout de lettres au tableau, vérifiez si la clé existe et si c'est le cas, ne l'ajoutez pas à nouveau.
2. Si les lettres supplémentaires sont acceptables, par exemple rent == renter, mais fernt! = Renter, vérifiez que les valeurs du tableau à la fin vérifient que 1 et -1 ne figurent pas simultanément dans le tableau. En d'autres termes, 1 et 0 seulement vont bien, ou -1 et 0 vont bien, mais pas 1 et -1 ne peuvent pas être dans le tableau en même temps.

Je ne sais pas à quelle vitesse cela se ferait par rapport à d'autres approches, mais ce serait facile à mettre en œuvre.

Answer 10

Je pense que vous devriez construire un arbre. J'ai écrit un peu de code python pour illustrer l'idée, mais c'est probablement un buggy:

class knot():
    def __init__(self, char, is_word, string = "" way = 0):
        self.children = []
        self.shortest_way = way
        self.char = char
        self.word = is_word
        self.string = string

def comparing(strings):
    sorted_strings = []
    for string in strings:
        array_of_string = []
        for char in string:
            array_of_string.append(char)
        sorted_strings.append(array_of_string.sort())
    sorted_strings.sort()

    start = []
    matches = []

    for array_of_string in sorted_strings:
        matches += insert_string(array_of_string, start)

def insert_string(array, start):
    for match_string in test_string(array, start):
        matches += (array, match_string.string)
    add_string(array, start, 0):

def add_string(array, knots, n):
    minimum = 0
    maximum = len(knots) - 1
    while minimum != maximum:
        num = int((minimum + maximum) / 2)
        if (knots[num].char > array[n]):
            minimum = num
        elif (knots[num].char < array[n]):
            maximum = num
        elif (knots[num].char == array[n]):
            return add_string(array, knots[num], n+1)
    knots.append(new_knots(array, n))
    knots.sort

    """ more insertion routine needed"""

def search_children(array, knots):
    minimum = 0
    maximum = len(knots) - 1
    while minimum != maximum:
        num = int((minimum + maximum) / 2)
        if (knots[num].char > array[0]):
            minimum = num
        elif (knots[num].char < array[0]):
            maximum = num
        elif (knots[num].char == array[0]):
            return test_string(array, knots[num])
    return []

def test_string(array, target_knot):
    if len(array) > target_knot.sortest_way + 1:
        return []
    match_knots = []
    if len(array) == 1 and target_knot.is_word == True:
        match_knots.append(target_knot)
    for i in range(1, len(array)):
        match_knots += search_children(array[i:], target_knot.children)
    return match_knots

Answer 11

En supposant que vous recherchiez uniquement des sous-ensembles et que vous vous limitiez aux lettres anglaises courantes, un histogramme efficace suffira. Je voudrais utiliser un entier non signé de 64 bits, avec 2 bits pour compter jusqu'à 2 occurrences et les 12 bits supplémentaires pour ajouter un indicateur de dépassement de capacité et pour compter jusqu'à 3 occurrences de 'e t a o n ns r h l d'. Les bits sont remplis plutôt que d'utiliser le binaire (donc, pour les 3 e, vous auriez 111, sinon vous avez besoin de quelque chose de plus compliqué que le binaire & Pour tester le confinement). Pour tester la relation de sous-ensemble, vous vérifiez le bit de débordement du sous-ensemble que vous testez et, s'il n'est pas défini, vous pouvez simplement l'utiliser au niveau du bit et pour tester le sous-ensemble. Revenez à la vérification de O (longueur) du contenu trié de la chaîne si l'histogramme déborde.

Answer 12

Quel que soit l'algorithme que vous choisissez, une optimisation peut être effectuée pour des chaînes de même longueur. Tout ce que vous avez à faire, c'est XOR pour chaque caractère. Si le résultat est 0, ils contiennent les mêmes lettres. Cela n’aidera pas dans le cas de la sous-chaîne, mais ce pourrait être une aide pour court-circuiter une comparaison plus coûteuse.