Złożoność homogenizacji łańcucha

Motywacja : Opracowując narzędzia do wersjonowania danych, zaczęliśmy szukać algorytmów do „różnicowania” dwóch zestawów liczb całkowitych, wymyślając sekwencję przekształceń, które przenoszą jeden zestaw liczb całkowitych na drugi. Udało nam się zredukować ten problem do następującego bardzo naturalnego problemu, który wydaje się mieć połączenia do edycji odległości, grupowania przez zamianę i minimalnej wspólnej partycji ciągów .

Problem : Otrzymujemy ciąg znaków, tzn. Ciąg liter, a naszym celem jest ujednolicenie go przy minimalnych kosztach. Oznacza to, że chcemy zmienić kolejność sekwencji, tak aby wszystkie podobne litery były obok siebie.

Jedyną dozwoloną operacją jest pobranie podsekwencji podobnych liter i przeniesienie tej podsekcji w dowolne miejsce, co kosztuje mnie 1 jednostkę.

Będziemy wdzięczni za wszelką pomoc charakteryzującą złożoność tego problemu!

Przykład :

• aabcdab: Input
• bcd aa ab: Po przeniesieniu pierwszego aa do pozycji tuż po „d”
• b bcdaaa: Po przesunięciu trailing b do pierwszej pozycji

Ponieważ powstały ciąg jest jednorodny, mamy koszt 2.

Zauważ, że nie jesteśmy w żaden sposób ograniczeni w odniesieniu do wyniku: dopóki jest on jednorodny, nie musimy zapewniać żadnej konkretnej kolejności.

Ten problem jest NP-zupełny dzięki redukcji z zestawu minimalnego trafienia .

Minimalny zestaw uderzania, daje nam świat, i szereg zestawów tak, że . Celem jest znalezienie najmniejszego rozmiaru, tak że taki, że .S ∀ s ∈ S , s ⊂ U H ⊂ U ∀ s ∈ S , ∃ h ∈ H h ∈ $U$$S$$\forall s \in S, s \subset U$$H \subset U$$\forall s \in S, \exists h \in H$$h \in s$

Redukcja jest następująca:

• Ciąg jest następujący: dla każdego elementu będą dwa znaki ciągu, . Pomiędzy tymi znakami będzie znak dla każdego tak, że . Pomiędzy parami znajdują się unikalne znaki, które nie są powtarzane w ciągu.U ' y " y ∈ S U ∈ s U $u \in U$$u'$$s'$$s \in S$$u \in s$$u'$

• Aby ujednolicić ciąg, znak musi zostać przesunięty razy, dla każdego . Dodatkowo, dla każdego , postać musi zostać przesunięta raz, chyba że wszystkie między parą zostały przeniesione gdzie indziej.| s | - 1 s u u ′ s ′ u $s'$$|s|-1$$s$$u$$u'$$s'$$u'$

• Dlatego, aby zminimalizować liczbę ruchów niezbędnych do ujednolicenia łańcucha, chcemy zmaksymalizować liczbę tak aby każdy został przeniesiony w inne miejsce. S, jeżeli s nie zostały przeniesione gdzie indziej muszą razem zawierają za każde , więc muszą one za zestaw uderzania. Co więcej, każdy taki zestaw uderzenie może służyć jako kończących lokalizacje s, przesuwając każdy do którego uderza go.s ′ u ′ s ′ s ′ s ∈ S s ′ s $u'$$s'$$u'$$s'$$s'$$s \in S$$s'$$s$$u$

• Zatem liczba ruchów do homogenizacji tego ciągu jest równa, gdzie jest minimalnym zestawem uderzeń.H $\sum |s| + |H^*|$$H^*$

Ponieważ minimalny zestaw uderzeń to NP-Hard, optymalna homogenizacja struny również jest. Ponieważ ruchy tworzą świadka, jest to NP-Complete.

Spójrz na liczbę zmian z jednej litery na drugą w swoim ciągu, które możesz postrzegać jako miarę niejednorodności łańcucha. Z każdym (użytecznym) ruchem podsekwencji zmniejszasz tę liczbę o jeden, jeśli podsekwencja, którą przenosisz, jest poprzedzona dwiema odrębnymi literami. W przeciwnym razie zmniejszysz niejednorodność o dwa.

Tak więc dla łańcucha ze zmianami k potrzebujesz najwyżej k - l + 1 ruchów, gdzie l jest liczbą różnych liter w łańcuchu, ponieważ na końcu pozostaną zmiany - 1 . Ponieważ ciąg długości n może mieć co najwyżej n-1 zmiany liter, może potrzebować co najwyżej n-l ruchów. Najmniejsza możliwa liczba to połowa tego.

Najlepsza strategia wydaje się zatem szukać podciągów postaci abbba i stamtąd odsunąć bbb. Jeśli nie ma już nic, przesuń cokolwiek. Nadal możesz próbować wykonywać te operacje, które tworzą nowe sytuacje abbba, ale myślę, że zysk będzie bardzo niewielki. Ponieważ najgorsza możliwa strategia (bez głupich ruchów, które zwiększają niejednorodność) wykorzystuje najwyżej dwa razy więcej ruchów niż optymalna, wydaje się, że niewiele, które możesz zyskać, nie ma żadnego uzasadnionego związku z wysiłkiem, jak odpowiedź Isaacga z charakterystyką jako NP-hard sugeruje. Chyba że tak naprawdę liczy się tylko liczba operacji ruchu i nie przejmujesz się czasem, aby zdecydować, które ruchy wykonać.

Najgorszym przypadkiem jest zatem ciąg znaków, w którym każda litera różni się od swojego poprzednika (i nie dostajesz żadnych premii abbba). Tutaj potrzebujesz wielu operacji liniowych na długości łańcucha i prawie równych tej długości.

W twoim przykładzie masz 5 -> 4 -> 3 zmiany, a 3 równa się liczbie liter (4) minus 1.

Uwaga dodatkowa: Dla alfabetu wielkości tylko dwóch każdy ruch, który nie przesuwa prefiksu lub sufiksu łańcucha, zmniejsza niejednorodność o dwa, a zatem każda sekwencja rozsądnych ruchów jest optymalna.