Задача 2 от брой 11/2004 - ИМЕНА - Анализ

Втора задача от конкурса (Shortest Superstring Problem) е NP пълна и за това целта е да се доближим колкото се може по-близко до оптималния отговор.

Нека overlap[i][j] е големината на най-големият низ които е надставка на име с индекс i и е представка на име с индекс j. Нека dist[i][j] е големината на представката оставаща не застъпена от най-голямото "напасване" м/у име с индекс i и име с индекс j т.е. d[i][j]=<големината на име с индекс i>-overlap[i][j].

Първата част от алгоритъма е да се намерят тези стойности т.к. от тях зависи апроксимацията която правя. Без ограничаване на общността може да приемем че в множеството от имена които са ни дадени няма такива които се съдържат напълно в други. d[i][j] както се вижда не е  проблем да се изчисли ако имаме overlap[i][j]. Моят метод който е подчинен на идеята на алгоритъма на Aho-Chorasick е да се подържа дърво със следните свойства :

1. на всяко ребро на дървото съответсва някоя буква
2. всеки път от корена до даден връх е представка или съвпада на някоя от дадените ни имена (като се разглеждат буквите по ребрата по които сме минали)
3. всички пътища са уникални т.е. не може да има два върха чиито път до тях да образуват един и същ низ
4. всеки връх Z съдържа "линк" (prefix[Z]) към друг връх с по малко ниво, така че пътя от корена до prefix[Z] е максимална надставка на низа образуван от пътя до Z.
5. всеки връх съдържа информация за това кои низове (имена) минават през този връх
6. отбелязваме кои върхове са терминални т.е. са край на име
7. коренът е на нулево ниво => големината на всеки низ образуван до даден връх е равна на нивото на върха

Overlap-а го правя по следния начин :

  for (всеки терминален връх o на име с индекс i)

   {

    w=o;

    while (1)

     {

      w=prefix[w];

      if (w е станало равно на корена на дървото) break;

      for (всички низове (имена) минаващи през връх w -> j)

       if (overlap[i][j]==0 /*ако не съм попълнил, защото първото попълване е най голямо*/)

        overlap[i][j]=нивото на връх w

     }  

   }

Това е идеята на алгоритъма, сега няколко думи по написването и сложността. Нека да сортираме всички имена лексикографски и дървото ще го строим ниво по ниво започвайки от корена. Всяко ниво пък ще изграждаме от ляво на дясно т.е. един път влезем ли във връх то ще направим всички необходими изчисления за него. Това строене става като въртя един цикъл за нивата и един за сортираните имена. Щом имената са сортирани то всички имена през даден връх ще бъдат последователни => за всеки връх ще пазим само началото и края на тази последователност. Друг осневен момент е намирането на максимална надставка на върха в който сме, щом строим дървото по нива то 100% ще съществува търсения връх.

Изчисляването на стойността става по подобие на KMP, т.е. вземаме върха към който води "линка" от бащата на сегашния връх (нека го кръстим t) и провераваме дали има ребро със същата буква която ни е завела към сегашния връх ако има то "линка" от сегашния връх сочи към върха до който отива намереното ребро ако няма то t=prefix[t] и повтаряме докато t е различно от корена.

Проверяването дали има ребро с дадена буква излизаща от някой връх става с двоично търсене по всички ребра на връха като аз държа в един линеен списък тези ребра.

И получаваме че сложността в най лошия случей е 512*4096*log26. Попълването на overlap е пак 512*4096*log26. (Знам че с амортизиран анализ се получават подобни стойности за сложността, но знам точно как)

Нека се върнем малко назад в премахването на низовете които се намират в други низове,

ако низа който трябва да махнем започва от началото на другия то лесно може да проверим това, ако ли не след като сме построили дървото проверяваме дали prefix[i] (за което и да е i) е терминален ако е то махаме низа които завърша в prefix[i].В общи линии това е първа част.

Моят отговор е най-малкия който някой от 3-те подхода е намерил. Първият е да вземаме два стринга които имат най-голям overlap и ги обединяваме това се повтаря докато остане само един низ и той е изходния, което става със сложност O(N*N*log(N*N)) идеята наподобява идеята за минимално покриващо дърво на Крускал.

Вторият е да направим минимално циклично покритие на dist (което става с унгарския алгоритъм) след това цепим всички цикли на местата където overlap-a м/у два съседни елемента е най-малък. Обединяваме низовете според наредбата от получения дотук граф и пускаме първия подход.

Третият е да направим максимално циклично покритие на overlap (което става с пак унгарския алгоритъм, но на всички стойности на overlap[i][j] им присвояваме overlap[i][j]=INF-overlap[i][j] и пускаме същата функция каквато пуснахме на dist. графа) след това цепим всички цикли на местата където overlap-a м/у два съседни елемента е най-малък. Обединяваме низовете според наредбата от графа и пускаме първия подход.

Не мога да кажа с точност колко добри резултати извежда всеки един подход, защото просто подбрах това което най-много ми хареса от строго детерминираните апросимационни алгоритми.

Забележка: Никъде не пиша за индексиране, но трябва да се подържа, защото имаме махане на низове, после сортиране и за изхода ще ни трябват оригиналните им индекси.

 References:

  [1] Arvim Blum ... Linear Approximation of Shortest Superstrings

  [2] Dany Breslauer ... Rotations of Periodic Strings and Short Superstrings

  [3] konkurs.musala.com

e-mail:rostislav_everest@yahoo.com

( Rostislav Rumenov )

За въпроси можете да ни пишете на адрес: konkurs@musala.com.

Supported by Musala Soft Ltd.

Copyright 2000-2010 by Musala Soft Ltd. All rights reserved.