Struktura danych lub algorytm do szybkiego znajdowania różnic między łańcuchami

19

Mam tablicę 100 000 ciągów o długości . Chcę porównać każdy ciąg z każdym innym, aby zobaczyć, czy dwa ciągi różnią się o 1 znak. W tej chwili, gdy dodam każdy ciąg do tablicy, sprawdzam go względem każdego łańcucha już w tablicy, który ma złożoność czasową . $k$ $\frac{n(n-1)}{2} k$

Czy istnieje struktura danych lub algorytm, który może porównywać ciągi ze sobą szybciej niż to, co już robię?

Niektóre dodatkowe informacje:

Sprawy porządku: abcdea xbcderóżnią się o 1 znak, podczas abcdei edcbaróżnią się o 4 znaków.
Dla każdej pary ciągów, które różnią się jednym znakiem, usunę jeden z tych ciągów z tablicy.
W tej chwili szukam ciągów, które różnią się tylko o 1 znak, ale byłoby miło, gdyby różnicę o 1 znak można było zwiększyć, powiedzmy, o 2, 3 lub 4 znaki. Jednak w tym przypadku uważam, że wydajność jest ważniejsza niż zdolność do zwiększenia limitu różnic postaci.
$k$ jest zwykle w zakresie 20–40.

algorithms data-structures program-optimization comparison JGut
źródło

4

Przeszukiwanie słownika ciągów z błędem 1 jest dość znanym problemem, np. Cs.nyu.edu/~adi/CGL04.pdf

KWillets

1

20-40 osób może zużyć sporo miejsca. Możesz spojrzeć na filtr Blooma ( en.wikipedia.org/wiki/Bloom_filter ), aby sprawdzić, czy zdegenerowane ciągi - zestaw wszystkich merów z jednego, dwóch lub więcej podstawień na merie testowej - są „być może w” lub „zdecydowanie” -not-in ”zestaw kilometrów. Jeśli pojawi się „być może”, następnie porównaj dwa ciągi, aby ustalić, czy jest to fałszywie dodatni. Przypadki „zdecydowanie nie w” są prawdziwymi negatywami, które zmniejszą ogólną liczbę porównań litera po literze, które należy wykonać, ograniczając porównania do potencjalnych potencjalnych trafień „być może”.

Alex Reynolds

Jeśli pracujesz z mniejszym zakresem k, możesz użyć zestawu bitów do przechowywania tabeli skrótów booleanów dla wszystkich zdegenerowanych łańcuchów (np. Github.com/alexpreynolds/kmer-boolean na przykład zabawka). Jednak dla k = 20-40 wymagania dotyczące miejsca dla zestawu bitów są po prostu zbyt duże.

Alex Reynolds

12

Możliwe jest osiągnięcie czasu najgorszego przypadku. $O(nk \log k)$

Zacznijmy prosto. Jeśli zależy Ci na łatwym do wdrożenia rozwiązaniu, które będzie wydajne na wielu nakładach, ale nie na wszystkich, oto proste, pragmatyczne, łatwe do wdrożenia rozwiązanie, które w praktyce wystarcza w wielu sytuacjach. W najgorszym przypadku jednak wraca do kwadratu.

Weź każdy ciąg i przechowuj go w tablicy mieszającej, wpisanej w pierwszej połowie łańcucha. Następnie iteruj po kubełkach z mieszaniem. Dla każdej pary ciągów w tym samym wiadrze sprawdź, czy różnią się one 1 znakiem (tj. Sprawdź, czy ich druga połowa różni się 1 znakiem).

Następnie weź każdy ciąg i zapisz go w tablicy mieszającej, tym razem wpisanej w drugiej połowie łańcucha. Ponownie sprawdź każdą parę ciągów w tym samym wiadrze.

Zakładając, że łańcuchy są dobrze rozłożone, czas działania będzie prawdopodobnie wynosił około . Ponadto, jeśli istnieje para ciągów, które różnią się o 1 znak, zostanie znaleziona podczas jednego z dwóch przebiegów (ponieważ różnią się tylko 1 znakiem, ten różniący się znak musi znajdować się w pierwszej lub drugiej połowie ciągu, więc druga lub pierwsza połowa łańcucha musi być taka sama). Jednak w najgorszym przypadku (np. Jeśli wszystkie ciągi znaków zaczynają się lub kończą tymi samymi znakami ), zmniejsza się to do czasu pracy , więc jego czas działania w najgorszym przypadku nie jest poprawą brutalnej siły . $O(nk)$ $k/2$ $O(n^2 k)$

W celu optymalizacji wydajności, jeśli jakikolwiek segment zawiera zbyt wiele łańcuchów, możesz powtórzyć ten sam proces rekurencyjnie, aby wyszukać parę, która różni się jednym znakiem. Wywołanie rekurencyjne będzie na ciągach o długości . $k/2$

Jeśli zależy Ci na najgorszym czasie działania:

Przy powyższej optymalizacji wydajności uważam, że najgorszym czasem działania jest . $O(nk \log k)$

DW
źródło

3

Jeśli ciągi

mają tę samą pierwszą połowę, co może się zdarzyć w prawdziwym życiu, to nie poprawiłeś złożoności.

Ω (n)

$\Omega(n)$

einpoklum

@einpoklum, jasne! Dlatego w drugim zdaniu napisałem stwierdzenie, że w najgorszym przypadku sprowadza się ono do kwadratu, a także stwierdzenie w moim ostatnim zdaniu opisujące, jak osiągnąć złożoność w najgorszym przypadku

jeśli cię to obchodzi o najgorszym przypadku. Ale chyba nie wyraziłem tego bardzo jasno - dlatego odpowiednio zredagowałem swoją odpowiedź. Czy teraz jest lepiej?

O (n k \log k)

$O(nk \log k)$

DW

15

Moje rozwiązanie jest podobne do j_random_hackera, ale używa tylko jednego zestawu skrótów.

Stworzyłbym zestaw skrótów ciągów. Dla każdego ciągu wejściowego dodaj do zestawu ciągów. W każdym z tych ciągów zastąp jedną z liter znakiem specjalnym, którego nie ma w żadnym z nich. Podczas ich dodawania sprawdź, czy nie ma ich jeszcze w zestawie. Jeśli tak, to masz dwa ciągi, które różnią się (najwyżej) jednym znakiem. $k$

Przykład z ciągami „abc”, „adc”

W przypadku abc dodajemy „* bc”, „a * c” i „ab *”

W przypadku adc dodajemy „* dc”, „a * c” i „ad *”

Kiedy dodamy „a * c” za drugim razem, zauważymy, że jest już w zestawie, więc wiemy, że istnieją dwa ciągi, które różnią się tylko jedną literą.

Całkowity czas działania tego algorytmu wynosi . Jest tak, ponieważ tworzymy nowych ciągów dla wszystkich ciągów na wejściu. Dla każdego z tych ciągów musimy obliczyć skrót, co zwykle zajmuje czas . $O(n*k^2)$ $k$ $n$ $O(k)$

Przechowywanie wszystkich ciągów zajmuje przestrzeń . $O(n*k^2)$

Dalsze doskonalenia

Możemy jeszcze bardziej ulepszyć algorytm, nie przechowując bezpośrednio zmodyfikowanych ciągów, ale zamiast tego przechowując obiekt z odniesieniem do oryginalnego ciągu i indeksu zamaskowanego znaku. W ten sposób nie musimy tworzyć wszystkich ciągów i potrzebujemy tylko miejsca do przechowywania wszystkich obiektów. $O(n*k)$

Będziesz musiał zaimplementować niestandardową funkcję skrótu dla obiektów. Możemy wziąć implementację Java jako przykład, zobacz dokumentację Java . Java hashCode zwielokrotnia wartość Unicode każdego znaku przez (przy długości łańcucha i indeksie jednego znaku. Zauważ, że każdy zmieniony łańcuch różni się tylko o jeden znak od oryginału. Możemy łatwo obliczyć wkład tego znaku w kod skrótu. Możemy go odjąć i dodać nasz znak maskowania. To wymaga do obliczenia. To pozwala nam obniżyć całkowity czas działania do $31^{k-i}$ $k$ $i$ $O(1)$ $O(n*k)$

Simon Prins
źródło

4

@JollyJoker Tak, kosmos jest przedmiotem zainteresowania tej metody. Możesz zmniejszyć przestrzeń, nie przechowując zmodyfikowanych ciągów, ale zamiast tego przechowując obiekt z odniesieniem do łańcucha i indeksu zamaskowanego. To powinno dać ci przestrzeń O (nk).

Simon Prins

Aby obliczyć skróty

dla każdego łańcucha w czasie

, myślę, że będziesz potrzebować specjalnej domowej funkcji haszującej (np. Oblicz hash oryginalnego łańcucha w czasie

, a następnie XOR z każdym usuniętym znaków za każdym razem w

(choć jest to prawdopodobnie całkiem zła funkcja skrótu na inne sposoby)). BTW, to jest całkiem podobne do mojego rozwiązania, ale z jednym hashtable zamiast

osobnych i zastępując znak „*” zamiast go usuwać.

k

$k$

O (k)

$O(k)$

O (k)

$O(k)$

O (1)

$O(1)$

k

$k$

j_random_hacker

@ SimonPrins Z niestandardowymi equalsi hashCodemetodami, które mogą działać. Samo utworzenie łańcucha w stylu a * b w tych metodach powinno uczynić go kuloodpornym; Podejrzewam, że niektóre inne odpowiedzi tutaj będą miały problemy z kolizją skrótu.

JollyJoker,

1

@DW Zmodyfikowałem swój post, aby odzwierciedlić fakt, że obliczanie skrótów zajmuje czas

i dodałem rozwiązanie sprowadzające całkowity czas działania z powrotem do

.

O (k)

$O(k)$

O (n * k)

$O(n*k)$

Simon Prins,

1

@ SimonPrins Najgorszym przypadkiem może być nk ^ 2 ze względu na sprawdzanie równości ciągów w hashset.contains, gdy mieszają się kolizje. Oczywiście najgorszy przypadek jest wtedy, gdy każdy ciąg ma dokładnie taki sam hash, co wymaga dość dużo ręcznie zbiór łańcuchów, zwłaszcza aby uzyskać ten sam hash dla *bc, a*c, ab*. Zastanawiam się, czy można to pokazać jako niemożliwe?

JollyJoker

7

Zrobiłbym tablic , z których każdy ma ciąg jako klucz i listę liczb (identyfikatorów ciągów) jako wartość. Tablica skrótów będzie zawierać wszystkie przetworzone do tej pory ciągi znaków, ale ze znakiem w pozycji usunięty . Na przykład, jeśli , wówczas będzie zawierać listę wszystkich dotychczas widzianych łańcuchów, które mają wzór $k$ $H_1, \dots, H_k$ $(k-1)$ $H_i$ $i$ $k=6$ $H_3[ABDEF]$ , gdzie oznacza „dowolny znak”. Następnie przetworzyć -tej ciąg wejściowy : $AB\cdot DEF$ $\cdot$ $j$ $s_j$

Dla każdego w zakresie od 1 do k :
- Utwórz ciąg , usuwając ty znak z . $s_j'$ $i$ $s_j$
- Spójrz w górę . Każdy identyfikator łańcucha tutaj identyfikuje oryginalny łańcuch, który jest albo równy , albo różni się tylko w pozycji . Wyjście takie jak mecze STRING . (Jeśli chcesz wykluczyć dokładne duplikaty, ustaw typ wartości tabeli hasht a na parę (identyfikator ciągu, usunięty znak), abyś mógł przetestować te, które zostały usunięte z tego samego znaku, który właśnie usunęliśmy z .) $H_i[s_j']$ $s$ $i$ $s_j$ $s_j$
- Wstaw do aby użyć przyszłych zapytań. $j$ $H_i$

Jeśli przechowujemy każdy klucz skrótu jawnie, musimy użyć przestrzeni i tym samym mieć co najmniej złożoność czasową. Ale jak opisano przez Simona Prinsa , możliwe jest reprezentowanie serii modyfikacji łańcucha (w jego przypadku opisanego jako zamiana pojedynczych znaków na , w moich jako usunięcie) niejawnie w taki sposób, że wszystkie kluczy skrótu dla określonego łańcucha muszą tylko spacja, prowadząca do ogólnej przestrzeni i otwierająca możliwość $O(nk^2)$ * $k$ $O(k)$ $O(nk)$ $O(nk)$ czas też. Aby osiągnąć tę złożoność czasową, potrzebujemy sposobu obliczenia skrótów dla wszystkich wariantów długości ciągu- w czasie : na przykład można to zrobić za pomocą skrótów wielomianowych, jak sugeruje DW (i to jest prawdopodobnie znacznie lepiej niż po prostu XORing usuniętego znaku za pomocą skrótu dla oryginalnego łańcucha). $k$ $k$ $O(k)$

Sztuczka niejawnej reprezentacji Simona Prinsa oznacza również, że „usunięcie” każdego znaku nie jest faktycznie wykonywane, więc możemy użyć zwykłej reprezentacji ciągu opartej na tablicy bez ograniczenia wydajności (zamiast połączonych list, jak pierwotnie sugerowałem).

j_random_hacker
źródło

2

Niezłe rozwiązanie. Przykładem odpowiedniej funkcji skrótu na zamówienie może być skrót wielomianowy.

DW

Dzięki @DW Czy możesz wyjaśnić, co masz na myśli przez „wielomianowy skrót”? Googlowanie tego terminu nie przyniosło mi niczego, co wydawałoby się ostateczne. (Jeśli chcesz, możesz edytować mój post bezpośrednio.)

j_random_hacker

1

Po prostu odczytaj ciąg jako podstawową liczbę

modulo

, gdzie

jest pewną liczbą pierwszą mniejszą niż rozmiar mapy skrótów, a

jest pierwotnym pierwiastkiem

, a

jest większe niż rozmiar alfabetu. Nazywa się to „mieszaniem wielomianowym”, ponieważ przypomina ocenę wielomianu, którego współczynniki są podane przez ciąg w

. Zostawię to jako ćwiczenie, aby dowiedzieć się, jak obliczyć wszystkie pożądane wartości skrótu w czasie

. Zauważ, że to podejście nie jest odporne na przeciwnika, chyba że losowo wybierzesz oba

spełniające pożądane warunki.

q

$q$

p

$p$

p

$p$

q

$q$

p

$p$

q

$q$

q

$q$

O (k)

$O(k)$

p, q

$p,q$

user21820

1

Myślę, że to rozwiązanie może być dalej udoskonalane przez obserwację, że tylko jedna z k potrzeb hash tables istnieć w tym samym czasie, co zmniejsza zapotrzebowanie na pamięć.

Michael Kay

1

@MichaelKay: To nie zadziała, jeśli chcesz obliczyć skróty

możliwych zmian ciągu w czasie

. Nadal musisz je gdzieś przechowywać. Więc jeśli sprawdzasz tylko jedną pozycję na raz, zajmiesz

razy tak długo, jakbyś sprawdzał wszystkie pozycje razem, używając

razy tyle wpisów hashtable.

k

$k$

O (k)

$O(k)$

k

$k$

k

$k$

user21820

2

Oto bardziej niezawodne podejście hashujące niż metoda wielomianowa. Najpierw wygenerować losowymi liczbami całkowitymi dodatnimi , które są względnie pierwsze z hashtable rozmiarze . Mianowicie, . Następnie mieszania każdy łańcuch na . Prawie nic nie może zrobić przeciwnik, aby spowodować bardzo nierównomierne kolizje, ponieważ generujesz czasie wykonywania i tak jak $k$ $r_{1..k}$ $M$ $0 \le r_i < M$ $x_{1..k}$ $(\sum_{i=1}^k x_i r_i ) \bmod M$ $r_{1..k}$ $k$ zwiększa maksymalne prawdopodobieństwo kolizji danych dwóch różnych łańcuchów szybko przechodzi do . Oczywiste jest również, jak obliczyć w czasie wszystkie możliwe wartości skrótu dla każdego łańcucha ze zmienionym jednym znakiem. $1/M$ $O(k)$

Jeśli naprawdę chcesz zagwarantować jednolite haszowanie, możesz wygenerować jedną losową liczbę naturalną mniejszą niż dla każdej pary dla od do i dla każdego znaku , a następnie haszować każdy ciąg do $r(i,c)$ $M$ $(i,c)$ $i$ $1$ $k$ $c$ $x_{1..k}$ $(\sum_{i=1}^k r(i,x_i) ) \bmod M$ . Wtedy prawdopodobieństwo kolizji z każdej pary różnych ciągów jest dokładnie . To podejście jest lepsze, jeśli twój zestaw znaków jest stosunkowo mały w porównaniu do . $1/M$ $n$

użytkownik21820
źródło

2

Wiele opublikowanych tutaj algorytmów zajmuje sporo miejsca na tablicach skrótów. Oto prosty algorytm pamięci dyskowej . $O(1)$ $O((n \lg n) \cdot k^2)$

Sztuką jest użycie , który jest komparatorem między dwiema wartościami i która zwraca wartość true, jeśli (leksykograficznie) zignoruje ty znak. Następnie algorytm jest następujący. $C_k(a, b)$ $a$ $b$ $a < b$ $k$

Po pierwsze, po prostu sortuj ciągi regularnie i wykonaj skanowanie liniowe, aby usunąć duplikaty.

Następnie dla każdego : $k$

Posortuj ciągi znaków za pomocą jako komparatora. $C_k$
Ciągi, które różnią się tylko są teraz sąsiadujące i można je wykryć w skanie liniowym. $k$

orlp
źródło

1

Dwa ciągi długości k , różniące się jednym znakiem, dzielą prefiks długości l i sufiks długości m taki, że k = l + m + 1 .

Odpowiedź Simona Prinsa koduje to, przechowując wszystkie kombinacje prefiksów / sufiksów jawnie, tzn. abcStaje się *bc, a*ci ab*. To k = 3, l = 0,1,2 i m = 2,1,0.

Jak wskazuje valarMorghulis, możesz organizować słowa w drzewie prefiksów. Istnieje również bardzo podobne drzewo sufiksów. Dość łatwo jest rozszerzyć drzewo o liczbę węzłów liści poniżej każdego przedrostka lub przyrostka; można to zaktualizować w O (k) podczas wstawiania nowego słowa.

Powodem, dla którego chcesz, aby liczba rodzeństwa była liczona, jest to, aby wiedzieć, biorąc pod uwagę nowe słowo, czy chcesz wyliczyć wszystkie ciągi z tym samym przedrostkiem, czy też wyliczyć wszystkie ciągi z tym samym przyrostkiem. Np. Dla „abc” jako danych wejściowych możliwe prefiksy to „”, „a” i „ab”, podczas gdy odpowiednie sufiksy to „bc”, „c” i „”. Jak widać, w przypadku krótkich sufiksów lepiej wyliczyć rodzeństwo w drzewie prefiksów i odwrotnie.

Jak wskazuje @einpoklum, z pewnością możliwe jest, że wszystkie ciągi mają ten sam przedrostek k / 2 . To nie jest problem w tym podejściu; drzewo prefiksów będzie liniowe do głębokości k / 2, a każdy węzeł do głębokości k / 2 będzie przodkiem 100 000 węzłów liści. W rezultacie drzewo sufiksów będzie używane do głębokości (k / 2-1), co jest dobre, ponieważ ciągi znaków muszą różnić się sufiksami, ponieważ mają wspólne prefiksy.

[edytuj] Jako optymalizacja, po określeniu najkrótszego unikalnego prefiksu ciągu, wiesz, że jeśli istnieje jeden inny znak, musi to być ostatni znak prefiksu, a po znalezieniu prawie duplikatu sprawdzanie prefiksu, który był o jeden krótszy. Jeśli więc „abcde” ma najkrótszy unikalny przedrostek „abc”, oznacza to, że istnieją inne ciągi zaczynające się od „ab?” ale nie z „abc”. Tj. Gdyby różniły się tylko jedną postacią, byłaby to trzecia postać. Nie musisz już sprawdzać „abc? E”.

Zgodnie z tą samą logiką, jeśli okaże się, że „cde” jest unikalnym najkrótszym sufiksem, to wiesz, że musisz sprawdzić tylko przedrostek o długości 2 „ab”, a nie przedrostek o długości 1 lub 3.

Zauważ, że ta metoda działa tylko dla dokładnie jednej różnicy między znakami i nie uogólnia do 2 różnic między znakami, polega na tym, że jeden jeden znak jest oddzieleniem identycznych przedrostków i identycznych przyrostków.

MSalters
źródło

s

$s$

1 \leq i \leq k

$1 \le i \le k$

P [s_{1}, \dots, s_{i - 1}]

$P[s_1, \dots, s_{i-1}]$

(i - 1)

$(i-1)$

S [s_{i + 1}, \dots, s_{k}]

$S[s_{i+1}, \dots, s_k]$

(k - i - 1)

$(k-i-1)$

O (1)

$O(1)$

1

k / 4

$k/4$

Pomysł optymalizacji jest sprytny i interesujący. Czy miałeś na myśli konkretny sposób sprawdzenia mtache? Jeśli „abcde” ma najkrótszy unikalny przedrostek „abc”, oznacza to, że powinniśmy sprawdzić inny ciąg znaków w postaci „ab? De”. Czy miałeś na myśli konkretny sposób, aby to zrobić? Jaki jest wynikowy czas działania?

DW

@DW: Chodzi o to, aby znaleźć ciągi znaków w postaci „ab? De”, sprawdzasz drzewo prefiksu, ile węzłów liści istnieje pod „ab”, a w drzewie sufiksu, ile węzłów istnieje pod „de”, a następnie wybierasz najmniejszy z dwóch do wyliczenia. Kiedy wszystkie ciągi zaczynają się i kończą tymi samymi znakami k / 4; oznacza to, że pierwsze węzły k / 4 w obu drzewach mają po jednym dziecku. I tak, za każdym razem, gdy potrzebujesz tych drzew, trzeba je pokonywać, co jest krokiem O (n * k).

MSalters

v

$v$

v

$v$

O (a h)

$O(ah)$

a

$a$

h

$h$

h

$h$

O (k)

$O(k)$

O (n)

$O(n)$

O (n k)

$O(nk)$ czas ogólny, ale powszechne są mniejsze alfabety. Ważna jest liczba dzieci (nie potomków), a także wzrost.

j_random_hacker

1

Przechowywanie ciągów w wiadrach jest dobrym sposobem (istnieją już różne odpowiedzi na ten temat).

Alternatywnym rozwiązaniem może być przechowywanie ciągów na posortowanej liście. Sztuką jest sortowanie według algorytmu mieszającego uwzględniającego lokalizację . Jest to algorytm mieszający, który daje podobne wyniki, gdy dane wejściowe są podobne [1].

$O(log(n))$ $O(n)$ $O(1)$ $O(n)$

Jednym z możliwych algorytmów mieszających wrażliwych na lokalizację może być Nilsimsa (z implementacją open source dostępną na przykład w Pythonie ).

[1]: Zauważ, że często algorytmy mieszające, takie jak SHA1, są zaprojektowane w odwrotny sposób: wytwarzają bardzo różne skróty dla podobnych, ale nie równych danych wejściowych.

Uwaga: Szczerze mówiąc, osobiście zaimplementowałbym jedno z zagnieżdżonych / zorganizowanych pod kątem drzew rozwiązań dla aplikacji produkcyjnych. Jednak pomysł posortowanej listy wydał mi się interesującą alternatywą. Zauważ, że ten algorytm w dużym stopniu zależy od wybranego algorytmu skrótu. Nilsimsa to jeden algorytm, który znalazłem - istnieje jednak wiele innych (na przykład TLSH, Ssdeep i Sdhash). Nie sprawdziłem, czy Nilsimsa działa z moim zarysowanym algorytmem.

tessi
źródło

1

Ciekawy pomysł, ale myślę, że musielibyśmy mieć pewne granice, jak daleko od siebie mogą się znajdować dwie wartości skrótu, gdy ich dane wejściowe różnią się tylko o 1 znak - a następnie skanować wszystko w tym zakresie wartości skrótu, a nie tylko sąsiadów. (Nie można mieć funkcji skrótu, która generuje sąsiednie wartości skrótu dla wszystkich możliwych par ciągów, które różnią się o 1 znak. Rozważmy ciągi o długości 2 w binarnym alfabecie: 00, 01, 10 i 11. Jeśli h (00) jest obok h (10) i h (01), to musi znajdować się między nimi, w takim przypadku h (11) nie może przylegać do nich obu i odwrotnie.

j_random_hacker

Patrzenie na sąsiadów nie wystarczy. Rozważ listę abcd, acef, agcd. Istnieje pasująca para, ale twoja procedura jej nie znajdzie, ponieważ abcd nie jest sąsiadem agcd.

DW

Oboje macie rację! Z sąsiadami nie miałem na myśli tylko „bezpośrednich sąsiadów”, ale myślałem o „sąsiedztwie” bliskich pozycji. Nie podałem, na ilu sąsiadów trzeba patrzeć, ponieważ zależy to od algorytmu mieszania. Ale masz rację, prawdopodobnie powinienem zanotować to w mojej odpowiedzi. dzięki :)

tessi

1

„LSH ... podobne elementy odwzorowują te same„ segmenty ”z dużym prawdopodobieństwem” - ponieważ jest to algorytm prawdopodobieństwa, wynik nie jest gwarantowany. Tak więc od TS zależy, czy potrzebuje 100% rozwiązania, czy 99,9% wystarczy.

Bulat

1

$O(nk+ n^2)$ $O(nk)$

$n$ $X = x_1.x_2.x_3 .... x_n$ $x_i, \forall 1 \le i \le n$ $X$

$x_i$ $(i-1)k$ $x_i$ $x_j$ $j<i$ $x_j$ $x_i = x_j$ $x_i[p] \ne x_j[p]$ $x_j$ $x_i$ $x_j$

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)
              }
            }
        }
    }
}

Możesz użyć biblioteki SDSL do zbudowania tablicy sufiksów w skompresowanej formie i odpowiedzi na zapytania LCP.

$X$ $O(nk)$ $O(n^2)$

$O(nk + qn^2)$ $q$

$j<i$ $j$

Ritu Kundu
źródło

O (k n^{2})

$O(kn^2)$ k

O (n k + n^{2})

$O(nk + n^2)$

O (k n^{2})

$O(kn^2)$

O (1)

$O(1)$

Chodzi mi o to, że k = 20..40 dla autora pytania i porównanie tak małych ciągów wymaga tylko kilku cykli procesora, więc praktyczna różnica między brutalną siłą a twoim podejściem prawdopodobnie nie istnieje.

Bulat

1

$O(nk)$ **bcdea*cde

Możesz także użyć tego podejścia, aby podzielić pracę na wiele rdzeni CPU / GPU.

Bulat
źródło

n = 100, 000

$n=100,000$

k \approx 40

$k\approx 40$

O (n k)

$O(nk)$

0

To jest krótka wersja odpowiedzi @ SimonPrins, która nie zawiera skrótów.

Zakładając, że żaden z łańcuchów nie zawiera gwiazdki:

$nk$ $k$ $\mathcal{O}(nk^2)$
$\mathcal{O}(nk^2\log nk)$
$\mathcal{O}(nk^2)$

Alternatywne rozwiązanie z niejawnym użyciem skrótów w Pythonie (nie może się oprzeć pięknu):

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
źródło

k

$k$

O (n k)

$O(nk)$

O (n^{2})

$\mathcal{O}(n^2)$

0

Oto moje zdanie na temat wyszukiwarki niezgodności 2+. Zauważ, że w tym poście uważam każdy łańcuch za okrągły, np. Podciąg o długości 2 przy indeksie k-1składa się z symbolu, str[k-1]po którym następuje str[0]. A podciąg o długości 2 przy indeksie -1jest taki sam!

Mk $mlen(k,M) = \lceil{k/M}\rceil-1$ Mk=20M=4abcd*efgh*ijkl*mnop*

Teraz algorytm wyszukiwania wszystkich niedopasowań do Msymboli wśród ciągów ksymboli:

dla każdego i od 0 do k-1
- podziel wszystkie ciągi na grupy według str[i..i+L-1], gdzie L = mlen(k,M). Jeśli L=4masz alfabet składający się tylko z 4 symboli (z DNA), utworzy to 256 grup.
- Grupy mniejsze niż ~ 100 ciągów można sprawdzić za pomocą algorytmu brute-force
- W przypadku większych grup powinniśmy wykonać podział wtórny:
  - Usuń z każdego łańcucha w Ljuż dopasowanych symbolach grupy
  - dla każdego j od i-L + 1 do kL-1
    - podziel wszystkie ciągi na grupy według str[i..i+L1-1], gdzie L1 = mlen(k-L,M). Fe, jeśli k=20, M=4, alphabet of 4 symbolstak L=4i L1=3to, utworzy 64 grupy.
    - resztę pozostawia jako ćwiczenie dla czytelnika: D

Dlaczego nie zaczynamy jod 0? Ponieważ już utworzyliśmy te grupy z tą samą wartością i, więc zadanie z j<=i-Lbędzie dokładnie równoważne zadaniu z zamienionymi wartościami i i.

Dalsze optymalizacje:

Na każdej pozycji rozważ także łańcuchy str[i..i+L-2] & str[i+L]. To tylko podwaja liczbę utworzonych miejsc pracy, ale pozwala na zwiększenie Lo 1 (jeśli moja matematyka jest poprawna). Tak więc fe zamiast 256 grup podzielisz dane na 1024 grupy.
$L[i]$ *0..k-1M-1k-1

Bulat
źródło

0

Codziennie pracuję nad wynalezieniem i optymalizacją alg, więc jeśli potrzebujesz ostatniej wydajności, oto plan:

Sprawdzaj z *każdą pozycją niezależnie, tj. Zamiast n*kwariantów ciągów przetwarzania pojedynczego zadania - uruchamiaj kniezależne zadania dla każdego sprawdzania nłańcucha. Możesz rozłożyć te kzadania na wiele rdzeni CPU / GPU. Jest to szczególnie ważne, jeśli chcesz sprawdzić różnice między znakami 2+. Mniejszy rozmiar zadania poprawi również lokalizację pamięci podręcznej, co samo w sobie może przyspieszyć program 10 razy.
Jeśli zamierzasz korzystać z tablic mieszających, użyj własnej implementacji wykorzystującej sondowanie liniowe i współczynnik obciążenia ~ 50%. Jest szybki i dość łatwy do wdrożenia. Lub użyj istniejącej implementacji z otwartym adresowaniem. Tabele skrótów STL są powolne ze względu na zastosowanie oddzielnego tworzenia łańcuchów.
Możesz spróbować wstępnie filtrować dane przy użyciu 3-stanowego filtra Blooma (rozróżniającego wystąpienia 0/1/1 +) zaproponowanego przez @AlexReynolds.
Dla każdego i od 0 do k-1 uruchom następujące zadanie:
- Wygeneruj 8-bajtowe struktury zawierające 4-5 bajtowy skrót każdego łańcucha (z *i-tą pozycją) i indeks łańcucha, a następnie albo posortuj je, albo utwórz tabelę skrótów z tych rekordów.

Do sortowania możesz wypróbować następującą kombinację:

pierwsze przejście to sortowanie radix MSD na 64-256 sposobów z wykorzystaniem sztuczki TLB
drugie przejście to sortowanie radix MSD na 256-1024 sposoby bez sztuczki TLB (łącznie 64 000 sposobów )
Trzeci przebieg to sortowanie wstawiane w celu usunięcia pozostałych niespójności

Bulat
źródło

Struktura danych lub algorytm do szybkiego znajdowania różnic między łańcuchami

Odpowiedzi: