Tengo una matriz de 100,000 cadenas, todas de longitud . Quiero comparar cada cadena con todas las demás para ver si dos cadenas difieren en 1 carácter. En este momento, a medida que agrego cada cadena a la matriz, la estoy verificando con cada cadena que ya está en la matriz, que tiene una complejidad temporal de .
¿Existe una estructura de datos o algoritmo que pueda comparar cadenas entre sí más rápido de lo que ya estoy haciendo?
Alguna información adicional:
El orden es importante:
abcde
yxbcde
difieren en 1 carácter, mientras queabcde
yedcba
diferir en 4 caracteres.Para cada par de cadenas que difieren en un carácter, eliminaré una de esas cadenas de la matriz.
En este momento, estoy buscando cadenas que difieran solo en 1 carácter, pero sería bueno que esa diferencia de 1 carácter se pudiera aumentar a, por ejemplo, 2, 3 o 4 caracteres. Sin embargo, en este caso, creo que la eficiencia es más importante que la capacidad de aumentar el límite de diferencia de caracteres.
suele estar en el rango de 20-40.
Respuestas:
Es posible lograrO ( n k logk ) peor tiempo de ejecución.
Comencemos simple. Si le importa una solución fácil de implementar que sea eficiente en muchas entradas, pero no en todas, aquí hay una solución simple, pragmática y fácil de implementar que muchas son suficientes en la práctica para muchas situaciones. Sin embargo, vuelve al tiempo de ejecución cuadrático en el peor de los casos.
Tome cada cadena y guárdela en una tabla hash, codificada en la primera mitad de la cadena. Luego, itera sobre los cubos de tabla hash. Para cada par de cadenas en el mismo grupo, verifique si difieren en 1 carácter (es decir, verifique si su segunda mitad difiere en 1 carácter).
Luego, toma cada cadena y guárdala en una tabla hash, esta vez tecleada en el segunda mitad de la cadena. Nuevamente revise cada par de cuerdas en el mismo cubo.
Suponiendo que las cadenas están bien distribuidas, el tiempo de ejecución probablemente será de . Además, si existe un par de cadenas que difieren en 1 carácter, se encontrará durante una de las dos pasadas (dado que difieren solo en 1 carácter, ese carácter diferente debe estar en la primera o segunda mitad de la cadena, entonces la segunda o primera mitad de la cadena debe ser la misma). Sin embargo, en el peor de los casos (p. Ej., Si todas las cadenas comienzan o terminan con los mismos caracteres k / 2 ), esto se degrada a O ( n 2 k )O ( n k ) k / 2 O(n2k) tiempo de ejecución, por lo que su peor tiempo de ejecución no es una mejora en la fuerza bruta .
Como una optimización del rendimiento, si algún depósito tiene demasiadas cadenas, puede repetir el mismo proceso de forma recursiva para buscar un par que difiera en un carácter. La invocación recursiva será en cadenas de longitud .k/2
Si le preocupa el peor tiempo de ejecución:
Con la optimización de rendimiento anterior, creo que el peor tiempo de ejecución es .O(nklogk)
fuente
Mi solución es similar a la de j_random_hacker pero usa solo un conjunto de hash.
Crearía un conjunto hash de cadenas. Para cada cadena en la entrada, agregue al conjuntok cadenas. En cada una de estas cadenas, reemplace una de las letras con un carácter especial, que no se encuentra en ninguna de las cadenas. Mientras los agrega, verifique que aún no estén en el conjunto. Si lo son, entonces tiene dos cadenas que solo difieren en (como máximo) un carácter.
Un ejemplo con las cadenas 'abc', 'adc'
Para abc agregamos '* bc', 'a * c' y 'ab *'
Para adc agregamos '* dc', 'a * c' y 'ad *'
Cuando agregamos 'a * c' la segunda vez, notamos que ya está en el conjunto, por lo que sabemos que hay dos cadenas que solo difieren en una letra.
El tiempo total de ejecución de este algoritmo es . Esto se debe a que creamos k nuevas cadenas para todas las n cadenas en la entrada. Para cada una de esas cadenas, necesitamos calcular el hash, que generalmente toma tiempo O ( k ) .O(n∗k2) k n O(k)
El almacenamiento de todas las cadenas ocupa espacio .O(n∗k2)
Futuras mejoras
Podemos mejorar aún más el algoritmo no almacenando las cadenas modificadas directamente, sino almacenando un objeto con una referencia a la cadena original y el índice del carácter que está enmascarado. De esta manera, no necesitamos crear todas las cadenas y solo necesitamos espacio para almacenar todos los objetos.O(n∗k)
Deberá implementar una función hash personalizada para los objetos. Podemos tomar la implementación de Java como ejemplo, consulte la documentación de Java . El código hash de Java multiplica el valor Unicode de cada carácter con (con k la longitud de la cadena e i el índice basado en uno). Tenga en cuenta que cada cadena alterada solo difiere en un carácter del original. Podemos calcular fácilmente la contribución de ese carácter al código hash. Podemos restar eso y agregar nuestro carácter de máscara en su lugar. Esto requiere O ( 1 ) para calcular. Esto nos permite reducir el tiempo total de ejecución a O ( n31k−i k i O(1) O(n∗k)
fuente
equals
yhashCode
que podrían funcionar. Simplemente crear la cadena de estilo a * b en esos métodos debería hacerlo a prueba de balas; Sospecho que algunas de las otras respuestas aquí tendrán problemas de colisión hash.*bc
,a*c
,ab*
. Me pregunto si podría mostrarse imposible.I would makek hashtables H1,…,Hk , each of which has a (k−1) -length string as the key and a list of numbers (string IDs) as the value. The hashtable Hi will contain all strings processed so far but with the character at position i deleted. For example, if k=6 , then H3[ABDEF] will contain a list of all strings seen so far that have the pattern AB⋅DEF , where ⋅ means "any character". Then to process the j -th input string sj :
If we store each hash key explicitly, then we must useO(nk2) space and thus have time complexity at least that. But as described by Simon Prins, it's possible to represent a series of modifications to a string (in his case described as changing single characters to k hash keys for a particular string need just O(k) space, leading to O(nk) space overall, and opening the possibility of O(nk) time too. To achieve this time complexity, we need a way to compute the hashes for all k variations of a length-k string in O(k) time: for example, this can be done using polynomial hashes, as suggested by D.W. (and this is likely much better than simply XORing the deleted character with the hash for the original string).
*
, in mine as deletions) implicitly in such a way that allSimon Prins's implicit representation trick also means that the "deletion" of each character is not actually performed, so we can use the usual array-based representation of a string without a performance penalty (rather than linked lists as I had originally suggested).
fuente
Here is a more robust hashtable approach than the polynomial-hash method. First generatek random positive integers r1 .. k that are coprime to the hashtable size METRO . Namely, 0 ≤ ryo< M . Then hash each string X1 .. k to ( ∑ki = 1Xyoryo) mod M . There is almost nothing an adversary can do to cause very uneven collisions, since you generate r1 .. k on run-time and so as k increases the maximum probability of collision of any given pair of distinct strings goes quickly to 1/M . It is also obvious how to compute in O(k) time all the possible hashes for each string with one character changed.
If you really want to guarantee uniform hashing, you can generate one random natural numberr(i,c) less than M for each pair (i,c) for i from 1 to k and for each character c , and then hash each string x1..k to (∑ki=1r(i,xi))modM . Then the probability of collision of any given pair of distinct strings is exactly 1/M . This approach is better if your character set is relatively small compared to norte .
fuente
A lot of the algorithms posted here use quite a bit of space on hash tables. Here's anO ( 1 ) auxiliary storage O ( ( n lgn ) ⋅ k2) runtime simple algorithm.
The trick is to useCk( a , b ) , which is a comparator between two values un and si that returns true if a < b (lexicographically) while ignoring the k th character. Then algorithm is as follows.
First, simply sort the strings regularly and do a linear scan to remove any duplicates.
Then, for eachk :
Sort the strings withCk as comparator.
Strings that differ only ink are now adjacent and can be detected in a linear scan.
fuente
Two strings of length k, differing in one character, share a prefix of length l and a suffix of length m such that k=l+m+1.
The answer by Simon Prins encodes this by storing all prefix/suffix combinations explicitly, i.e.
abc
becomes*bc
,a*c
andab*
. That's k=3, l=0,1,2 and m=2,1,0.As valarMorghulis points out, you can organize words in a prefix tree. There's also the very similar suffix tree. It's fairly easy to augment the tree with the number of leaf nodes below each prefix or suffix; this can be updated in O(k) when inserting a new word.
The reason you want these sibling counts is so you know, given a new word, whether you want to enumerate all strings with the same prefix or whether to enumerate all strings with the same suffix. E.g. for "abc" as input, the possible prefixes are "", "a" and "ab", while the corresponding suffixes are "bc", "c" and "". As it obvious, for short suffixes it's better to enumerate siblings in the prefix tree and vice versa.
As @einpoklum points out, it's certainly possible that all strings share the same k/2 prefix. That's not a problem for this approach; the prefix tree will be linear up to depth k/2 with each node up to k/2 depth being the ancestor of 100.000 leaf nodes. As a result, the suffix tree will be used up to (k/2-1) depth, which is good because the strings have to differ in their suffixes given that they share prefixes.
[edit] As an optimization, once you've determined the shortest unique prefix of a string, you know that if there's one different character, it must be the last character of the prefix, and you'd have found the near-duplicate when checking a prefix that was one shorter. So if "abcde" has a shortest unique prefix "abc", that means there are other strings that start with "ab?" but not with "abc". I.e. if they'd differ in only one character, that would be that third character. You don't need to check for "abc?e" anymore.
By the same logic, if you would find that "cde" is a unique shortest suffix, then you know you need to check only the length-2 "ab" prefix and not length 1 or 3 prefixes.
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.
fuente
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 (takingO(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.
fuente
One could achieve the solution inO(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,
Build the enhanced suffix array of all then strings concatenated together. Let X=x1.x2.x3....xn where xi,∀1≤i≤n is a string in the collection. Build the suffix array and LCP array for X .
Now eachxi starts at position (i−1)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.
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 ofX 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 isO(nk+qn2) where q is the number of allowed mismatches.
If you wish to remove a string from the collection, instead of checking everyj<i , you could keep a list of only 'valid' j .
fuente
k
en esta fórmula prácticamente se puede omitir, ya que con SSE puede contar bytes coincidentes en 2 ciclos de CPU por 16 símbolos (es decir, 6 ciclos para k = 40).Una mejora para todas las soluciones propuestas. Todos requierenO ( n k ) memoria en el peor de los casos. Puede reducirlo calculando hashes de cadenas con
*
cada carácter, es decir*bcde
,a*cde
... y procesando en cada pasada solo variantes con valor hash en cierto rango entero. Fe con valores de hash pares en la primera pasada y valores de hash impares en la segunda.También puede usar este enfoque para dividir el trabajo entre múltiples núcleos de CPU / GPU.
fuente
Esta es una versión corta de la respuesta de @SimonPrins que no involucra hashes.
Suponiendo que ninguna de sus cadenas contenga un asterisco:
Una solución alternativa con el uso implícito de hashes en Python (no puede resistir la belleza):
fuente
Aquí está mi opinión sobre 2+ buscadores de desajustes. Tenga en cuenta que en esta publicación considero que cada cadena es circular, la subcadena fe de longitud 2 en el índice
k-1
consiste en un símbolostr[k-1]
seguido destr[0]
. ¡Y la subcadena de longitud 2 en el índice-1
es la misma!Si tenemosm l e n ( k , M) = ⌈ k / M⌉ - 1 dado que, en el peor de los casos, los símbolos que no coinciden dividen la cadena (circular) en
M
desajustes entre dos cadenas de longitudk
, tienen una subcadena coincidente con una longitud de al menosM
segmentos de igual tamaño. Fe conk=20
yM=4
el "peor" partido puede tener el patrónabcd*efgh*ijkl*mnop*
.Ahora, el algoritmo para buscar todos los desajustes hasta los
M
símbolos entre cadenas dek
símbolos:str[i..i+L-1]
, dondeL = mlen(k,M)
. Fe siL=4
y tiene un alfabeto de solo 4 símbolos (del ADN), esto hará 256 grupos.L
símbolos de grupo que ya coincidimosstr[i..i+L1-1]
, dondeL1 = mlen(k-L,M)
. Fe sik=20, M=4, alphabet of 4 symbols
, asíL=4
y asíL1=3
, esto formará 64 grupos.¿Por qué no comenzamos
j
desde 0? Debido a que ya formamos estos grupos con el mismo valor dei
, entonces el trabajo conj<=i-L
será exactamente equivalente al trabajo con los valores i y j intercambiados.Otras optimizaciones:
str[i..i+L-2] & str[i+L]
. Esto solo duplica la cantidad de trabajos creados, pero permite aumentarL
en 1 (si mis cálculos son correctos). Entonces, fe en lugar de 256 grupos, dividirá los datos en 1024 grupos.*
truco: para cada i in0..k-1
, elimine el i-ésimo símbolo de cada cadena y cree trabajos en busca deM-1
desajustes en esas cadenas de longitudk-1
.fuente
Trabajo todos los días para inventar y optimizar algos, por lo que si necesita hasta el último rendimiento, ese es el plan:
*
en cada posición de forma independiente, es decir, en lugar den*k
variantes de cadena de procesamiento de trabajo único : iniciek
trabajos independientes para cadan
cadena de verificación . Puede distribuir estosk
trabajos entre múltiples núcleos de CPU / GPU. Esto es especialmente importante si va a verificar 2+ char diffs. Un tamaño de trabajo más pequeño también mejorará la localidad de caché, que por sí sola puede hacer que el programa sea 10 veces más rápido.*
la posición i-ésima) e índice de cadena, y luego ordénelos o cree una tabla hash a partir de estos registros.Para ordenar, puede probar el siguiente combo:
fuente