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

10

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.

Aditya Parameswaran
źródło

Odpowiedzi:

6

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 sUSsS,sUHUsS,hHhs

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 'uUussSusu

  • 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|1suusu

  • 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 uususssSssu

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

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

isaacg
źródło
To elegancka obniżka - dziękuję!
Aditya Parameswaran
2

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.

Peter Leupold
źródło
Twierdzisz, że ruch może zmniejszyć liczbę zmian maksymalnie o 2, ale w rzeczywistości może zmniejszyć liczbę zmian nawet o 3. Na przykład, konwersję „aabcabc” na „aaabbcc” poprzez przeniesienie pierwszego podłańcucha „bc” do środek drugiego podłańcucha „bc” powoduje zmniejszenie liczby zmian w łańcuchu z 5 do 2.
Michaił Rudoy
Cześć, @MikhailRudoy. W pytaniach stwierdza się, że operacja polega na „zbieraniu podsekwencji podobnych do siebie liter”, więc bc nie jest dozwolone, o ile rozumiem.
Peter Leupold
Całkowicie mi brakowało tego szczegółu. Masz rację w tym przypadku.
Mikhail Rudoy
Piotr ma rację: te ruchy są niedozwolone.
Aditya Parameswaran
Re: reszta odpowiedzi - w rzeczy samej, te spostrzeżenia dotyczą: dolnych granic, optymalności wielkości liter alfabetu 2 i heurystyki dla tego, co robić w dowolnym momencie, są cenne. Ponieważ każdy ruch w najgorszym przypadku korzysta tylko z tej sekwencji liter, aw najlepszym przypadku łączy co najwyżej dwie sekwencje liter, tak jak w abbba, przybliżenie 2 wydaje się naturalne.
Aditya Parameswaran