Structure de données ou algorithme pour trouver rapidement les différences entre les chaînes

19

J'ai un tableau de 100 000 cordes, toutes de longueur k . Je veux comparer chaque chaîne à chaque autre chaîne pour voir si deux chaînes différentes diffèrent d'un caractère. En ce moment, comme j'ajoute chaque chaîne au tableau, je le compare à chaque chaîne déjà dans le tableau, qui a une complexité temporelle de n(n1)2k.

Existe-t-il une structure de données ou un algorithme qui peut comparer les chaînes les unes aux autres plus rapidement que ce que je fais déjà?

Quelques informations supplémentaires:

  • L'ordre est important: abcdeet xbcdediffère de 1 caractère, abcdeet edcbadiffère de 4 caractères.

  • Pour chaque paire de chaînes qui diffèrent d'un caractère, je supprimerai l'une de ces chaînes du tableau.

  • En ce moment, je recherche des chaînes qui ne diffèrent que par 1 caractère, mais ce serait bien si cette différence de 1 caractère pouvait être augmentée à, disons, 2, 3 ou 4 caractères. Cependant, dans ce cas, je pense que l'efficacité est plus importante que la capacité d'augmenter la limite de différence de caractères.

  • k est généralement compris entre 20 et 40.

JGut
la source
4
La recherche d'un dictionnaire de chaînes avec 1 erreur est un problème assez connu, par exemple cs.nyu.edu/~adi/CGL04.pdf
KWillets
1
20-40mers peuvent utiliser un peu d'espace. Vous pouvez regarder un filtre Bloom ( en.wikipedia.org/wiki/Bloom_filter ) pour tester si des chaînes dégénérées - l'ensemble de tous les mers d'une, deux ou plusieurs substitutions sur un test mer - sont "peut-être" ou "définitivement" -not-in "un ensemble de kmers. Si vous obtenez un "peut-être", comparez davantage les deux chaînes pour déterminer s'il s'agit ou non d'un faux positif. Les cas "définitivement non inclus" sont de véritables négatifs qui réduiront le nombre total de comparaisons lettre par lettre que vous devez faire, en limitant les comparaisons aux seuls hits "peut-être" potentiels.
Alex Reynolds
Si vous travaillez avec une plus petite plage de k, vous pouvez utiliser un jeu de bits pour stocker une table de hachage de booléens pour toutes les chaînes dégénérées (par exemple github.com/alexpreynolds/kmer-boolean pour le jouet par exemple). Pour k = 20-40, cependant, l'espace requis pour un jeu de bits est tout simplement trop.
Alex Reynolds

Réponses:

12

Il est possible d'atteindre pire des cas.O(nklogk)

Commençons simple. Si vous vous souciez d'une solution facile à implémenter qui sera efficace sur de nombreuses entrées, mais pas sur toutes, voici une solution simple, pragmatique et facile à implémenter qui suffit en pratique pour de nombreuses situations. Cependant, cela revient au temps de fonctionnement quadratique dans le pire des cas.

Prenez chaque chaîne et stockez-la dans une table de hachage, calée sur la première moitié de la chaîne. Ensuite, parcourez les compartiments de table de hachage. Pour chaque paire de chaînes dans le même compartiment, vérifiez si elles diffèrent en 1 caractère (c'est-à-dire, vérifiez si leur seconde moitié diffère en 1 caractère).

Ensuite, prenez chaque chaîne et stockez-la dans une table de hachage, cette fois sur la seconde moitié de la chaîne. Vérifiez à nouveau chaque paire de cordes dans le même seau.

En supposant que les chaînes sont bien réparties, le temps d'exécution sera probablement d'environ . De plus, s'il existe une paire de chaînes qui diffèrent d'un caractère, on la trouvera lors de l'une des deux passes (puisqu'elles diffèrent d'un seul caractère, ce caractère différent doit être dans la première ou la seconde moitié de la chaîne, la deuxième ou la première moitié de la chaîne doit donc être la même). Cependant, dans le pire des cas (par exemple, si toutes les chaînes commencent ou se terminent avec les mêmes caractères k / 2 ), cela se dégrade en temps d'exécution O ( n 2 k ) , donc son temps d'exécution le plus défavorable n'est pas une amélioration de la force brute .O(nk)k/2O(n2k)

En tant qu'optimisation des performances, si un compartiment contient trop de chaînes, vous pouvez répéter le même processus de manière récursive pour rechercher une paire qui diffère d'un caractère. L'invocation récursive se fera sur des chaînes de longueur .k/2

Si vous vous souciez du pire temps de fonctionnement:

Avec l'optimisation des performances ci-dessus, je crois que le temps d'exécution le plus défavorable est .O(nklogk)

DW
la source
3
Si les chaînes partagent la même première moitié, ce qui peut très bien se produire dans la vie réelle, alors vous n'avez pas amélioré la complexité. Ω(n)
einpoklum
@einpoklum, bien sûr! C'est pourquoi j'ai écrit dans ma deuxième phrase la déclaration selon laquelle cela revient au temps de fonctionnement quadratique dans le pire des cas, ainsi que la déclaration dans ma dernière phrase décrivant comment atteindre la complexité du pire des cas si vous vous souciez sur le pire des cas. Mais je suppose que je n'ai peut-être pas exprimé cela très clairement - j'ai donc modifié ma réponse en conséquence. Est-ce mieux maintenant? O(nklogk)
DW
15

Ma solution est similaire à celle de j_random_hacker mais n'utilise qu'un seul ensemble de hachage.

Je créerais un ensemble de chaînes de hachage. Pour chaque chaîne de l'entrée, ajoutez à l'ensemble des chaînes. Dans chacune de ces chaînes, remplacez l'une des lettres par un caractère spécial, introuvable dans aucune des chaînes. Pendant que vous les ajoutez, vérifiez qu'ils ne sont pas déjà dans l'ensemble. S'ils le sont, vous avez deux chaînes qui ne diffèrent que par (au plus) un caractère.k

Un exemple avec les chaînes 'abc', 'adc'

Pour abc, nous ajoutons '* bc', 'a * c' et 'ab *'

Pour adc, nous ajoutons '* dc', 'a * c' et 'ad *'

Lorsque nous ajoutons 'a * c' la deuxième fois, nous remarquons qu'il est déjà dans l'ensemble, nous savons donc qu'il y a deux chaînes qui ne diffèrent que par une lettre.

Le temps de fonctionnement total de cet algorithme est . C'est parce que nous créons k nouvelles chaînes pour toutes les n chaînes dans l'entrée. Pour chacune de ces chaînes, nous devons calculer le hachage, ce qui prend généralement O ( k ) .O(nk2)knO(k)

Le stockage de toutes les chaînes prend un espace .O(nk2)

Améliorations supplémentaires

Nous pouvons améliorer encore l'algorithme en ne stockant pas directement les chaînes modifiées mais en stockant plutôt un objet avec une référence à la chaîne d'origine et l'index du caractère masqué. De cette façon, nous n'avons pas besoin de créer toutes les chaînes et nous n'avons besoin que de l' espace pour stocker tous les objets.O(nk)

Vous devrez implémenter une fonction de hachage personnalisée pour les objets. Nous pouvons prendre l'implémentation Java comme exemple, voir la documentation java . Le java hashCode multiplie la valeur unicode de chaque caractère par (avec k la longueur de la chaîne et i l'index à base unique du caractère. Notez que chaque chaîne modifiée ne diffère que d'un caractère de l'original. Nous pouvons facilement calculer la contribution de ce caractère au code de hachage. Nous pouvons soustraire cela et ajouter notre caractère de masquage à la place. Cela prend O ( 1 ) à calculer. Cela nous permet de ramener la durée totale de fonctionnement à O ( n31kikiO(1)O(nk)

Simon Prins
la source
4
@JollyJoker Oui, l'espace est quelque chose de préoccupant avec cette méthode. Vous pouvez réduire l'espace en ne stockant pas les chaînes modifiées, mais en stockant plutôt un objet avec une référence à la chaîne et à l'index masqué. Cela devrait vous laisser un espace O (nk).
Simon Prins
Pour calculer les hachages pour chaque chaîne en temps O ( k ) , je pense que vous aurez besoin d'une fonction de hachage maison spéciale (par exemple, calculer le hachage de la chaîne d'origine en O ( k ) temps, puis XOR avec chacun des supprimés caractères en O ( 1 ) fois chacun (bien que ce soit probablement une fonction de hachage assez mauvaise à d'autres égards)). BTW, c'est assez similaire à ma solution, mais avec une seule table de hachage au lieu de k distinctes, et en remplaçant un caractère par "*" au lieu de le supprimer. kO(k)O(k)O(1)k
j_random_hacker
Avec @SimonPrins sur mesure equalset des hashCodeméthodes qui pourraient fonctionner. La simple création de la chaîne de style a * b dans ces méthodes devrait la rendre à l'épreuve des balles; Je soupçonne que certaines des autres réponses ici auront des problèmes de collision de hachage.
JollyJoker
1
@DW J'ai modifié mon message pour refléter le fait que le calcul des hachages prend du temps et j'ai ajouté une solution pour ramener le temps de fonctionnement total à O ( n k ) . O(k)O(nk)
Simon Prins
1
@SimonPrins Le pire des cas pourrait être nk ^ 2 en raison de la vérification de l'égalité des chaînes dans hashset.contains lorsque les hachages entrent en collision. Bien sûr, le pire des cas est quand chaque chaîne a le même hachage exacte, ce qui nécessiterait un ensemble à peu près fabriqués à la main des cordes, en particulier pour obtenir le même hachage pour *bc, a*c, ab*. Je me demande si cela pourrait être démontré impossible?
JollyJoker
7

Je ferais tables de hachage H 1 , , H k , chacune ayant une chaîne de longueur ( k - 1 ) comme clé et une liste de nombres (ID de chaîne) comme valeur. La table de hachage H i contiendra toutes les chaînes traitées jusqu'à présent mais avec le caractère à la position i supprimé . Par exemple, si k = 6kH1,,Hk(k1)Hiik=6 , alors contiendra une liste de toutes les chaînes vues jusqu'ici qui ont le modèle AH3[ABDEF] , où signifie "n'importe quel caractère". Ensuite, pour traiter la j- ème chaîne d'entrée s j :ABDEFjsj

  1. Pour chaque compris entre 1 et k : ik
    • Former la chaîne en supprimant le i- ème caractère de s j .sjisj
    • Recherchez . Chaque ID de chaîne identifie ici une chaîne d'origine qui est soit égale à s , soit différente à la position iHi[sj]si uniquement. Sortez-les comme correspondances pour la chaîne . (Si vous souhaitez exclure les doublons exacts, faites du type de valeur des tables de hachage une paire (ID de chaîne, caractère supprimé), afin de pouvoir tester celles qui ont supprimé le même caractère que nous venons de supprimer de s j .)sjsj
    • Insérez dans H i pour les futures requêtes à utiliser.jHi

Si nous stockons explicitement chaque clé de hachage, alors nous devons utiliser l' espace et donc avoir au moins la complexité temporelle. Mais comme décrit par Simon Prins , il est possible de représenter une série de modifications à une chaîne (dans son cas décrit comme changeant des caractères simples en , dans le mien comme des suppressions) implicitement de telle manière que toutes les k clés de hachage pour une chaîne particulière aient juste besoin O ( k ) espace, menant aussi au O. O(nk2)*kO(k) espace global, et ouvrant la possibilité de O ( n k )O(nk)O(nk)temps aussi. Pour atteindre cette complexité temporelle, nous avons besoin d'un moyen de calculer les hachages pour toutes les variations d'une chaîne de longueur k en temps O ( k ) : par exemple, cela peut être fait en utilisant des hachages polynomiaux, comme suggéré par DW (et c'est probablement beaucoup mieux que simplement XOR le caractère supprimé avec le hachage de la chaîne d'origine).kkO(k)

L'astuce de représentation implicite de Simon Prins signifie également que la «suppression» de chaque caractère n'est pas réellement effectuée, nous pouvons donc utiliser la représentation habituelle basée sur un tableau d'une chaîne sans pénalité de performance (plutôt que des listes liées comme je l'avais initialement suggéré).

j_random_hacker
la source
2
Belle solution. Un exemple de fonction de hachage sur mesure appropriée serait un hachage polynomial.
DW
Merci @DW Pourriez-vous peut-être clarifier un peu ce que vous entendez par "hachage polynomial"? Googler le terme ne m'a rien donné de définitif. (N'hésitez pas à modifier mon article directement si vous le souhaitez.)
j_random_hacker
1
Il suffit de lire la chaîne comme un nombre de base modulo p , où p est un nombre premier inférieur à la taille de votre table de hachage, et q est une racine primitive de p , et q est supérieur à la taille de l'alphabet. On l'appelle "hachage polynomial" car c'est comme évaluer le polynôme dont les coefficients sont donnés par la chaîne en q . Je vais le laisser comme un exercice pour comprendre comment calculer tous les hachages souhaités en temps O ( k ) . Notez que cette approche n'est pas à l'abri d'un adversaire, sauf si vous choisissez au hasard les deux p , q satisfaisant aux conditions souhaitées.qppqpqqO(k)p,q
user21820
1
Je pense que cette solution peut être encore affinée en observant qu'une seule des k tables de hachage doit exister à la fois, réduisant ainsi les besoins en mémoire.
Michael Kay
1
@MichaelKay: Cela ne fonctionnera pas si vous voulez calculer les hachages des altérations possibles d'une chaîne en temps O ( k ) . Vous devez toujours les stocker quelque part. Donc, si vous ne cochez qu'une seule position à la fois, vous prendrez k fois autant de temps que si vous vérifiez toutes les positions ensemble en utilisant k fois autant d'entrées de table de hachage. kO(k)kk
user21820
2

Voici une approche de table de hachage plus robuste que la méthode de hachage polynomial. Tout d' abord générer des nombres entiers positifs aléatoires r 1 .. k qui sont premiers entre eux à la taille table de hachage M . À savoir, 0 r i < M . Ensuite , chaque chaîne de hachage x 1 .. k à ( Σ k i = 1 x i r i ) mod M . Un adversaire ne peut presque rien faire pour provoquer des collisions très inégales, puisque vous générez r 1 .. kkr1..kM0ri<Mx1..k(i=1kxiri)modMr1..k au moment de l'exécution et donc kaugmente la probabilité maximale de collision selon l' une quelconque paire donnée de chaînes distinctes passe rapidement à . Il est également évident de calculer en O ( k1/M tous les hachages possibles pour chaque chaîne avec un caractère changé.O(k)

Si vous voulez vraiment garantir un hachage uniforme, vous pouvez générer un nombre naturel aléatoire inférieur à M pour chaque paire ( i , c ) pour i de 1 à k et pour chaque caractère c , puis hacher chaque chaîne x 1 .. k à ( k i = 1 r ( i , x i ) ) mod Mr(i,c)M(i,c)i1kcx1..k(i=1kr(i,xi))modM. La probabilité de collision d'une paire donnée de chaînes distinctes est exactement . Cette approche est meilleure si votre jeu de caractères est relativement petit par rapport à n .1/Mn

user21820
la source
2

De nombreux algorithmes publiés ici utilisent un peu d'espace sur les tables de hachage. Voici un algorithme simple d'exécution de stockage auxiliaire O ( ( n lg n ) k 2 ) .O(1)O((nlgn)k2)

L'astuce consiste à utiliser , qui est un comparateur entre deux valeurs a et b qui renvoie vrai si a < b (lexicographiquement) tout en ignorant le k ème caractère. L'algorithme est alors le suivant.Ck(a,b)aba<bk

Tout d'abord, triez simplement les chaînes régulièrement et effectuez un balayage linéaire pour supprimer les doublons.

Ensuite, pour chaque :k

  1. Triez les chaînes avec comme comparateur.Ck

  2. Les chaînes qui ne diffèrent que par sont désormais adjacentes et peuvent être détectées dans un balayage linéaire.k

orlp
la source
1

Deux chaînes de longueur k , différant par un caractère, partagent un préfixe de longueur l et un suffixe de longueur m tels que k = l + m + 1 .

La réponse de Simon Prins l'encode en stockant explicitement toutes les combinaisons préfixe / suffixe, c'est-à-dire abcdevient *bc, a*cet ab*. C'est k = 3, l = 0,1,2 et m = 2,1,0.

Comme le souligne valarMorghulis, vous pouvez organiser les mots dans une arborescence de préfixes. Il y a aussi l'arbre des suffixes très similaire. Il est assez facile d'augmenter l'arborescence avec le nombre de nœuds feuilles sous chaque préfixe ou suffixe; cela peut être mis à jour dans O (k) lors de l'insertion d'un nouveau mot.

La raison pour laquelle vous souhaitez que ces nombres de frères et sœurs soit que vous sachiez, étant donné un nouveau mot, si vous voulez énumérer toutes les chaînes avec le même préfixe ou si vous devez énumérer toutes les chaînes avec le même suffixe. Par exemple, pour "abc" en entrée, les préfixes possibles sont "", "a" et "ab", tandis que les suffixes correspondants sont "bc", "c" et "". Comme il est évident, pour les suffixes courts, il est préférable d'énumérer les frères et sœurs dans l'arborescence des préfixes et vice versa.

Comme le souligne @einpoklum, il est certainement possible que toutes les chaînes partagent le même préfixe k / 2 . Ce n'est pas un problème pour cette approche; l'arbre de préfixe sera linéaire jusqu'à la profondeur k / 2, chaque nœud jusqu'à la profondeur k / 2 étant l'ancêtre de 100 000 nœuds foliaires. Par conséquent, l'arborescence des suffixes sera utilisée jusqu'à la profondeur (k / 2-1), ce qui est bien car les chaînes doivent différer dans leurs suffixes étant donné qu'elles partagent des préfixes.

[edit] Comme optimisation, une fois que vous avez déterminé le préfixe unique le plus court d'une chaîne, vous savez que s'il y a un caractère différent, ce doit être le dernier caractère du préfixe, et vous auriez trouvé le quasi-doublon quand vérifier un préfixe plus court. Donc, si "abcde" a le préfixe unique le plus court "abc", cela signifie qu'il existe d'autres chaînes commençant par "ab?" mais pas avec "abc". C'est-à-dire que s'ils différaient en un seul caractère, ce serait ce troisième caractère. Vous n'avez plus besoin de vérifier "abc? E".

Par la même logique, si vous trouvez que "cde" est un suffixe unique le plus court, alors vous savez que vous devez vérifier uniquement le préfixe "ab" de longueur 2 et non les préfixes de longueur 1 ou 3.

Note that this method works only for exactly one character differences and does not generalize to 2 character differences, it relies one one character being the separation between identical prefixes and identical suffixes.

MSalters
la source
Are you suggesting that for each string s and each 1ik, we find the node P[s1,,si1] corresponding to the length-(i1) prefix in the prefix trie, and the node S[si+1,,sk] corresponding to the length-(ki1) suffix in the suffix trie (each takes amortised O(1) time), and compare the number of descendants of each, choosing whichever has fewer descendants, and then "probing" for the rest of the string in that trie?
j_random_hacker
1
What is the running time of your approach? It looks to me like in the worst case it might be quadratic: consider what happens if every string starts and ends with the same k/4 characters.
D.W.
The optimization idea is clever and interesting. Did you have in mind a particular way to do the check for mtaches? If the "abcde" has the shortest unique prefix "abc", that means we should check for some other string of the form "ab?de". Did you have in mind a particular way to do that, that will be efficient? What's the resulting running time?
D.W.
@D.W.: The idea is that to find strings in the form "ab?de", you check the prefix tree how many leaf nodes exist below "ab" and in the suffix tree how many nodes exist under "de", then choose the smallest of the two to enumerate. When all strings begin and end with the same k/4 characters; that means the first k/4 nodes in both trees have one child each. And yes, every time you need those trees, those have to be traversed which is an O(n*k) step.
MSalters
To check for a string of the form "ab?de" in the prefix trie, it suffices to get to the node for "ab", then for each of its children v, check whether the path "de" exists below v. That is, don't bother enumerating any other nodes in these subtries. This takes O(ah) time, where a is the alphabet size and h is the height of the initial node in the trie. h is O(k), so if the alphabet size is O(n) then it is indeed O(nk) time overall, but smaller alphabets are common. The number of children (not descendants) is important, as well as the height.
j_random_hacker
1

Storing strings in buckets is a good way (there are already different answers outlining this).

An alternative solution could be to store strings in a sorted list. The trick is to sort by a locality-sensitive hashing algorithm. This is a hash algorithm which yields similar results when the input is similar[1].

Each time you want to investigate a string, you could calculate its hash and lookup the position of that hash in your sorted list (taking O(log(n)) for arrays or O(n) for linked lists). If you find that the neighbours (considering all close neighbours, not only those with an index of +/- 1) of that position are similar (off by one character) you found your match. If there are no similar strings, you can insert the new string at the position you found (which takes O(1) for linked lists and O(n) for arrays).

One possible locality-sensitive hashing algorithm could be Nilsimsa (with open source implementation available for example in python).

[1]: Note that often hash algorithms, like SHA1, are designed for the opposite: producing greatly differing hashes for similar, but not equal inputs.

Disclaimer: To be honest, I would personally implement one of the nested/tree-organized bucket-solutions for a production application. However, the sorted list idea struck me as an interesting alternative. Note that this algorithm highly depends on the choosen hash algorithm. Nilsimsa is one algorithm I found - there are many more though (for example TLSH, Ssdeep and Sdhash). I haven't verified that Nilsimsa works with my outlined algorithm.

tessi
la source
1
Interesting idea, but I think we would need to have some bounds on how far apart two hash values can be when their inputs differ by just 1 character -- then scan everything within that range of hash values, instead of just neighbours. (It's impossible to have a hash function that produces adjacent hash values for all possible pairs of strings that differ by 1 character. Consider the length-2 strings in a binary alphabet: 00, 01, 10 and 11. If h(00) is adjacent to both h(10) and h(01) then it must be between them, in which case h(11) can't be adjacent to them both, and vice versa.)
j_random_hacker
Looking at neighbors isn't sufficient. Consider the list abcd, acef, agcd. There exists a matching pair, but your procedure will not find it, as abcd is not a neighbor of agcd.
D.W.
You both are right! With neighbours I didn't mean only "direct neighbours" but thought of "a neighbourhood" of close positions. I didn't specify how many neighbours need to be looked at since that depends on the hash algorithm. But you're right, I should probably note this down in my answer. thanks :)
tessi
1
"LSH... similar items map to the same “buckets” with high probability" - since it's probability algorithm, result isn't guaranteed. So it depends on TS whether he needs 100% solution or 99.9% is enough.
Bulat
1

One could achieve the solution in O(nk+n2) time and O(nk) space using enhanced suffix arrays (Suffix array along with the LCP array) that allows constant time LCP (Longest Common Prefix) query (i.e. Given two indices of a string, what is the length of the longest prefix of the suffixes starting at those indices). Here, we could take advantage of the fact that all strings are of equal length. Specifically,

  1. Build the enhanced suffix array of all the n strings concatenated together. Let X=x1.x2.x3....xn where xi,1in is a string in the collection. Build the suffix array and LCP array for X.

  2. Now each xi starts at position (i1)k in the zero-based indexing. For each string xi, take LCP with each of the string xj such that j<i. If LCP goes beyond the end of xj then xi=xj. Otherwise, there is a mismatch (say xi[p]xj[p]); in this case take another LCP starting at the corresponding positions following the mismatch. If the second LCP goes beyond the end of xj then xi and xj differ by only one character; otherwise there are more than one mismatches.

    for (i=2; i<= n; ++i){
        i_pos = (i-1)k;
        for (j=1; j < i; ++j){
            j_pos = (j-1)k;
            lcp_len = LCP (i_pos, j_pos);
            if (lcp_len < k) { // mismatch
                if (lcp_len == k-1) { // mismatch at the last position
                // Output the pair (i, j)
                }
                else {
                  second_lcp_len = LCP (i_pos+lcp_len+1, j_pos+lcp_len+1);
                  if (lcp_len+second_lcp_len>=k-1) { // second lcp goes beyond
                    // Output the pair(i, j)
                  }
                }
            }
        }
    }
    

You could use SDSL library to build the suffix array in compressed form and answer the LCP queries.

Analysis: Building the enhanced suffix array is linear in the length of X i.e. O(nk). Each LCP query takes constant time. Thus, querying time is O(n2).

Generalisation: This approach can also be generalised to more than one mismatches. In general, running time is O(nk+qn2) where q is the number of allowed mismatches.

If you wish to remove a string from the collection, instead of checking every j<i, you could keep a list of only 'valid' j.

Ritu Kundu
la source
Can i say that O(kn2) algo is trivial - just compare each string pair and count number of matches? And k in this formula practically can be omitted, since with SSE you can count matching bytes in 2 CPU cycles per 16 symbols (i.e. 6 cycles for k=40).
Bulat
Apologies but I could not understand your query. The above approach is O(nk+n2) and not O(kn2). Also, it is virtually alphabet-size independent. It could be used in conjunction with the hash-table approach -- Once two strings are found to have the same hashes, they could be tested if they contain a single mismatch in O(1) time.
Ritu Kundu
My point is that k=20..40 for the question author and comparing such small strings require only a few CPU cycles, so practical difference between brute force and your approach probably doesn't exist.
Bulat
1

One improvement to all the solutions proposed. They all require O(nk) memory in the worst case. You can reduce it by computing hashes of strings with * instead each character, i.e. *bcde, a*cde... and processing at each pass only variants with hash value in certain integer range. F.e. with even hash values in the first pass, and odd hash values in the second one.

You can also use this approach to split the work among multiple CPU/GPU cores.

Bulat
la source
Clever suggestion! In this case, the original question says n=100,000 and k40, so O(nk) memory doesn't seem likely to be an issue (that might be something like 4MB). Still a good idea worth knowing if one needs to scale this up, though!
DW
0

This is a short version of @SimonPrins' answer not involving hashes.

Assuming none of your strings contain an asterisk:

  1. Create a list of size nk where each of your strings occurs in k variations, each having one letter replaced by an asterisk (runtime O(nk2))
  2. Sort that list (runtime O(nk2lognk))
  3. Check for duplicates by comparing subsequent entries of the sorted list (runtime O(nk2))

An alternative solution with implicit usage of hashes in Python (can't resist the beauty):

def has_almost_repeats(strings,k):
    variations = [s[:i-1]+'*'+s[i+1:] for s in strings for i in range(k)]
    return len(set(variations))==k*len(strings)
Bananach
la source
Thanks. Please also mention the k copies of exact duplicates, and I'll +1. (Hmm, just noticed I made the same claim about O(nk) time in my own answer... Better fix that...)
j_random_hacker
@j_random_hacker I don't know what exactly the OP wants reported, so I left step 3 vague but I think it is trivial with some extra work to report either (a) a binary any duplicate/no duplicates result or (b) a list of pairs of strings that differ in at most one position, without duplicates. If we take the OP literally ("...to see if any two strings..."), then (a) seems to be desired. Also, if (b) were desired then of course simply creating a list of pairs may take O(n2) if all strings are equal
Bananach
0

Here is my take on 2+ mismatches finder. Note that in this post I consider each string as circular, f.e. substring of length 2 at index k-1 consists of symbol str[k-1] followed by str[0]. And substring of length 2 at index -1 is the same!

If we have M mismatches between two strings of length k, they have matching substring with length at least mlen(k,M)=k/M1 since, in the worst case, mismatched symbols split (circular) string into M equal-sized segments. F.e. with k=20 and M=4 the "worst" match may have the pattern abcd*efgh*ijkl*mnop*.

Now, the algorithm for searching all mismatches up to M symbols among strings of k symbols:

  • for each i from 0 to k-1
    • split all strings into groups by str[i..i+L-1], where L = mlen(k,M). F.e. if L=4 and you have alphabet of only 4 symbols (from DNA), this will make 256 groups.
    • Groups smaller than ~100 strings can be checked with brute-force algorithm
    • For larger groups, we should perform secondary division:
      • Remove from every string in the group L symbols we already matched
      • for each j from i-L+1 to k-L-1
        • split all strings into groups by str[i..i+L1-1], where L1 = mlen(k-L,M). F.e. if k=20, M=4, alphabet of 4 symbols, so L=4 and L1=3, this will make 64 groups.
        • the rest is left as exercise for the reader :D

Why we don't start j from 0? Because we already made these groups with the same value of i, so job with j<=i-L will be exactly equivalent to job with i and j values swapped.

Further optimizations:

  • At every position, also consider strings str[i..i+L-2] & str[i+L]. This only doubles amount of jobs created, but allows to increase L by 1 (if my math is correct). So, f.e. instead of 256 groups, you will split data into 1024 groups.
  • If some L[i] becomes too small, we can always use the * trick: for each i in in 0..k-1, remove i'th symbol from each string and create job searching for M-1 mismatches in those strings of length k-1.
Bulat
la source
0

I work everyday on inventing and optimizing algos, so if you need every last bit of performance, that is the plan:

  • Check with * in each position independently, i.e. instead of single job processing n*k string variants - start k independent jobs each checking n strings. You can spread these k jobs among multiple CPU/GPU cores. This is especially important if you are going to check 2+ char diffs. Smaller job size will also improve cache locality, which by itself can make program 10x faster.
  • If you are going to use hash tables, use your own implementation employing linear probing and ~50% load factor. It's fast and pretty easy to implement. Or use an existing implementation with open addressing. STL hash tables are slow due to use of separate chaining.
  • You may try to prefilter data using 3-state Bloom filter (distinguishing 0/1/1+ occurrences) as proposed by @AlexReynolds.
  • For each i from 0 to k-1 run the following job:
    • Generate 8-byte structs containing 4-5 byte hash of each string (with * at i-th position) and string index, and then either sort them or build hash table from these records.

For sorting, you may try the following combo:

  • first pass is MSD radix sort in 64-256 ways employing TLB trick
  • second pass is MSD radix sort in 256-1024 ways w/o TLB trick (64K ways total)
  • third pass is insertion sort to fix remaining inconsistencies
Bulat
la source