У меня есть массив из 100 000 строк, все длиной . Я хочу сравнить каждую строку с любой другой строкой, чтобы увидеть, отличаются ли любые две строки на 1 символ. Прямо сейчас, когда я добавляю каждую строку в массив, я проверяю ее по каждой строке, уже находящейся в массиве, которая имеет временную сложность .
Есть ли структура данных или алгоритм, который может сравнивать строки друг с другом быстрее, чем то, что я уже делаю?
Некоторая дополнительная информация:
Порядок имеет значение:
abcde
иxbcde
отличается на 1 символ, аabcde
иedcba
отличается на 4 символа.Для каждой пары строк, которые отличаются на один символ, я буду удалять одну из этих строк из массива.
Сейчас я ищу строки, которые отличаются только на 1 символ, но было бы хорошо, если бы эта разница в 1 символ могла быть увеличена, скажем, до 2, 3 или 4 символов. Тем не менее, в этом случае, я думаю, эффективность важнее, чем способность увеличивать лимит различий между персонажами.
обычно находится в диапазоне 20-40.
Ответы:
Можно достичьO ( n k logк ) наихудшего времени работы.
Давайте начнем с простого. Если вам нужно простое в реализации решение, которое будет эффективным на многих входах, но не на всех, вот простое, прагматичное, простое в реализации решение, которого на практике достаточно для многих ситуаций. Однако в худшем случае он возвращается к квадратичному времени работы.
Возьмите каждую строку и сохраните ее в хеш-таблице с ключом в первой половине строки. Затем выполните итерации по хеш-таблицам. Для каждой пары строк в одном и том же сегменте проверьте, отличаются ли они на 1 символ (т. Е. Проверьте, отличается ли их вторая половина на 1 символ).
Затем возьмите каждую строку и сохраните ее в хеш-таблице, на этот раз с ключом во второй половине строки. Снова проверьте каждую пару строк в одном ведре.
Предполагая, что строки хорошо распределены, время выполнения, вероятно, будет около . Более того, если существует пара строк, которые отличаются на 1 символ, она будет найдена во время одного из двух проходов (поскольку они отличаются только на 1 символ, этот различающийся символ должен находиться либо в первой, либо во второй половине строки, поэтому вторая или первая половина строки должна быть одинаковой). Однако в худшем случае (например, если все строки начинаются или заканчиваются одинаковыми k / 2 символами), это ухудшает время выполнения O ( n 2 k ) , поэтому его время выполнения в худшем случае не является улучшением грубой силы ,O ( n k ) k/2 O(n2k)
В качестве оптимизации производительности, если в одном сегменте слишком много строк, вы можете рекурсивно повторить один и тот же процесс, чтобы найти пару, отличающуюся одним символом. Рекурсивный вызов будет выполняться для строк длиной .k/2
Если вам небезразлично время работы в худшем случае:
С учетом вышеописанной оптимизации производительности, я считаю, что наихудшее время выполнения - .O(nklogk)
источник
Мое решение похоже на j_random_hacker's, но использует только один хэш-набор.
Я бы создал хеш-набор строк. Для каждой строки во входе добавьте в набор строк. В каждой из этих строк замените одну из букв специальным символом, которого нет ни в одной из строк. Пока вы добавляете их, убедитесь, что их нет в наборе. Если они есть, то у вас есть две строки, которые отличаются только (максимум) одним символом.k
Пример со строками 'abc', 'adc'
Для abc мы добавляем '* bc', 'a * c' и 'ab *'
Для adc мы добавляем '* dc', 'a * c' и 'ad *'
Когда мы добавляем 'a * c' во второй раз, мы замечаем, что он уже находится в наборе, поэтому мы знаем, что есть две строки, которые отличаются только одной буквой.
Общее время работы этого алгоритма составляет . Это потому, что мы создаем k новых строк для всех n строк на входе. Для каждой из этих строк нам нужно вычислить хеш, который обычно занимает O ( k ) времени.O(n∗k2) k n O(k)
Хранение всех строк занимает пространства.O(n∗k2)
Дальнейшие улучшения
Мы можем улучшить алгоритм дальше, не сохраняя измененные строки напрямую, а вместо этого сохраняя объект со ссылкой на исходную строку и индекс маскируемого символа. Таким образом, нам не нужно создавать все строки, и нам нужно только место для хранения всех объектов.O(n∗k)
Вам нужно будет реализовать пользовательскую хеш-функцию для объектов. Мы можем взять реализацию Java в качестве примера, см. Документацию по Java . Java hashCode умножает значение Юникода каждого символа на (с k длиной строки и i индексом, основанным на одном символе. Обратите внимание, что каждая измененная строка отличается только на один символ от оригинала. Мы можем легко вычислить вклад этого символа в хэш-код. Мы можем вычесть это и добавить вместо этого наш маскирующий символ. Для вычисления требуется O ( 1 ) . Это позволяет нам сократить общее время выполнения до O ( n31k−i k i O(1) O(n∗k)
источник
equals
иhashCode
методами, которые могут работать. Простое создание строки в стиле * в этих методах должно сделать ее пуленепробиваемой; Я подозреваю, что у некоторых других ответов здесь будут проблемы столкновения хэша.*bc
,a*c
,ab*
. Интересно, можно ли это показать невозможным?Я бы сделал хеш-таблиц H 1 , … , H k , каждая из которых имеет строку длиной ( k - 1 ) в качестве ключа и список чисел (идентификаторов строк) в качестве значения. Хеш-таблица H i будет содержать все строки, которые были обработаны до сих пор, но символ в позиции i удален . Например, если k = 6 , то H 3 [ A B D E F ] будет содержать список всех рассмотренных до сих пор строк, имеющих шаблон Ak H1,…,Hk (k−1) Hi i k=6 H3[ABDEF] , где ⋅ означает «любой символ». Затем для обработки j-й входной строки s j :AB⋅DEF ⋅ j sj
Если мы храним каждый хэш-ключ явно, то мы должны использовать пространство и, таким образом, иметь временную сложность, по крайней мере, такую. Но, как описано Саймоном Принсом , можно представить серию модификаций строки (в его случае описанную как изменение отдельных символов на , в моем случае как удаление) неявным образом, так что все k ключей хеш-функции для конкретной строки должны просто O ( k ) пространство, приводящее к O ( n k ) пространству в целом, и открывающее возможность O ( n k )O(nk2) k O(k) O(nk) O(nk) время тоже. Чтобы достичь этой временной сложности, нам нужен способ для вычисления хэшей для всех вариаций строки длины k за время O ( k ) : например, это может быть сделано с использованием полиномиальных хэшей, как предлагает DW (и это скорее всего, гораздо лучше, чем просто XOR для удаленного символа с хешем для исходной строки).k k O(k)
*
Уловка неявного представления Саймона Принса также означает, что «удаление» каждого символа фактически не выполняется, поэтому мы можем использовать обычное представление строки на основе массива без снижения производительности (вместо связанных списков, как я изначально предлагал).
источник
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 M . Namely, 0≤ri<M . Then hash each string x1..k to (∑ki=1xiri)modM . 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 n .
источник
A lot of the algorithms posted here use quite a bit of space on hash tables. Here's anO(1) auxiliary storage O((nlgn)⋅k2) runtime simple algorithm.
The trick is to useCk(a,b) , which is a comparator between two values a and b 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.
источник
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.
источник
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.
источник
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 .
источник
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).One improvement to all the solutions proposed. They all requireO(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.
источник
This is a short version of @SimonPrins' answer not involving hashes.
Assuming none of your strings contain an asterisk:
An alternative solution with implicit usage of hashes in Python (can't resist the beauty):
источник
Вот мой взгляд на 2+ несоответствия искателя. Обратите внимание, что в этом посте я рассматриваю каждую строку как круговую, например подстрока длины 2 в индексе
k-1
состоит из символа,str[k-1]
за которым следуетstr[0]
. И подстрока длины 2 в индексе-1
одинакова!Если у нас естьм л е н ( к , М) = ⌈ к / м⌉ - 1 поскольку в худшем случае несоответствующие символы разбивают (круговую) строку на
M
несоответствия между двумя строками длиныk
, они имеют совпадающую подстроку длиной не менееM
сегменты одинакового размера. Fe сk=20
иM=4
«худший» матч может иметь образецabcd*efgh*ijkl*mnop*
.Теперь алгоритм поиска всех несоответствий до
M
символов среди строкk
символов:str[i..i+L-1]
, гдеL = mlen(k,M)
. Например, если уL=4
вас есть алфавит только из 4 символов (из ДНК), это составит 256 групп.L
символы, которые мы уже сопоставилиstr[i..i+L1-1]
, гдеL1 = mlen(k-L,M)
. Fe , еслиk=20, M=4, alphabet of 4 symbols
, такL=4
иL1=3
, это сделает 64 групп.Почему мы не начинаем
j
с 0? Поскольку мы уже создали эти группы с одинаковым значениемi
, поэтому работа сj<=i-L
будет точно эквивалентна работе с заменой значений i и j.Дальнейшая оптимизация:
str[i..i+L-2] & str[i+L]
. Это только удваивает количество созданных рабочих мест, но позволяет увеличитьL
на 1 (если моя математика верна). Таким образом, например, вместо 256 групп, вы разделите данные на 1024 группы.*
хитрость: для каждого i in in0..k-1
удалите i-й символ из каждой строки и создайте работу, ищаM-1
несоответствия в этих строках длиныk-1
.источник
I work everyday on inventing and optimizing algos, so if you need every last bit of performance, that is the plan:
*
in each position independently, i.e. instead of single job processingn*k
string variants - startk
independent jobs each checkingn
strings. You can spread thesek
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.*
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:
источник