[Algorytm LCS] Dla wielu ciągów

Odpowiedz Nowy wątek
2010-08-25 16:06

Rejestracja: 12 lat temu

Ostatnio: 3 lata temu

0

Witajcie, przeszukałem forum ale niestety nie natrafiłem na żaden ślad który pomógłby mi w rozwiązaniu problemu. Otóż piszę aplikację która ma implementować algorytm wyszukiwania najdłuższego podciągu ALE dla wielu ciągów. Dla dwóch znam, bo linków w google jest aż za dużo. Natomiast nigdzie nie mogłem znaleźć dla 3 i więcej ciągów jak również nie mam żadnego pomysłu.

Pozostało 580 znaków

donki7
2010-08-26 19:16
donki7
0

http://en.wikipedia.org/wiki/[...]_problem#LCS_function_defined

Tu jest wzór na LCS. Gdy zastosujesz spamiętywanie, to ten kod można zapisać w C++ czy podobnym niemal bezpośrednio (dochodzi tylko case: jeśli wartość już obliczona to ją zwróć).

Dorobienie trzeciej zmiennej, Zj jest raczej trywialne:

  • warunek w drugiej linii zmieniamy na: if xi = yj = zk
  • akcję w drugiej linii zamieniamy na: (LCS(Xi-1, Yj-1, Zk-1) + x)
  • warunek w ostatniej linii zamieniamy po prostu na else - w zasadzie ten warunek zachowuje się dokładnie tak jak else,
  • akcję w trzeciej linii zamieniamy na: longest(LCS(Xi-1, Yj-1, Zk), LCS(Xi-1, Yj, Zk-1), LCS(Xi, Yj-1, Zk-1))

Po wykonaniu algorytmu dostaniesz LCS w komórce Xm, Yn, Zo.

Zamiana tego na postać dynamiczną jest trywialna jeśli ma się kod dla wersji dwuwymiarowej.

Dla n stringów algorytm wymaga tablicy n wymiarowej!!!

Np dla piętnastu stringów stuznakowych wymaga 100 ^ 15 komórek :)

Pozostało 580 znaków

2010-08-26 23:50

Rejestracja: 12 lat temu

Ostatnio: 3 lata temu

0

Rozumiem mniej więcej co napisałeś, tylko sęk w tym, że ja potrzebuję taki algorytm który będzie mógł obsłużyć dowolną ilość ciągów wejściowych (przykladowo 5 czy 7) a nie że ja na "sztywno" napiszę funkcję.

Pozostało 580 znaków

donkey
2010-08-27 00:00
donkey
0

No to zamiast tablicy wielowymiarowej możesz:

  • zrobić tablicę stałowymiarową (np jednowymiarową) i bawić się z indeksami,
  • zrobić haszmapę list (czy tam wektorów) mapującą listę współrzędnych na zawartość elementu - cholernie wolne ale eleganckie,

Dla przyspieszenia możesz wygenerować sztywny kod dla małych n.

Ewentualnie może da się to obejść za pomocą metaprogramowania, ale to już zależy od języka.

Pozostało 580 znaków

2010-08-27 00:22

Rejestracja: 12 lat temu

Ostatnio: 3 lata temu

0

W zadaniu mam wykorzystać programowanie dynamiczne. Ten algorytm na wiki by się nadawał właśnie tylko że jest on dla 2 ciągów.

Pozostało 580 znaków

donkey
2010-08-27 01:38
donkey
0

No to zostaje zabawa ze wskaźnikami / indeksami.

Np zamiast:

int a[5][10][15];
a[3][4][7] = 8;

zrobić:

int a[5 * 10 * 15];
a[(3*10 + 4)*15 + 7] = 8;

Można to nawet mocno przyspieszyć. Odległość pomiędzy &LCS[x, y, z] i &LCS[x - 1, y, z] jest stała, podobnie dla reszty przypadków. Można więc sobie te odległości stablicować. Kod wyjdzie równie elegancki co w przypadku szczególnym (tzn ustalony wymiar) :)

Pozostało 580 znaków

donki7
2010-08-27 19:37
donki7
0
/* 
 * File:   main.cpp
 * Author: Piotrek
 *
 * Created on 27 sierpień 2010, 17:52
 */

#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <string>
#include <vector>

using namespace std;

vector<string> A;
vector<int> L;
int *LCS;
int cellsNum;
int *distances;
int sumDistances;
int N;

bool hasZero(int *indexes) {
    bool result = false;
    for (int i = 0; (!result) && (i < N); i++) {
        result |= indexes[i] == 0;
    }
    return result;
}

bool equal(int *indexes) {
    bool result = true;
    for (int i = 1; result && (i < N); i++) {
        result &= A[i - 1][indexes[i - 1]] == A[i][indexes[i]];
    }
    return result;
}

int longest(int index) {
    int result = 0;
    for (int i = 0; i < N; i++) {
        if (LCS[index - distances[i]] > result) {
            result = LCS[index - distances[i]];
        }
    }
    return result;
}

void nextIndex(int *indexes) {
    for (int i = N - 1; i >= 0; i--) {
        indexes[i]++;
        if (indexes[i] == L[i]) {
            indexes[i] = 0;
        } else {
            break;
        }
    }
}

void computeLCS() {
    int *indexes = new int[N];
    for (int i = 0; i < N; i++) {
        indexes[i] = 0;
    }
    for (int i = 0; i < cellsNum; i++) {
        if (LCS[i] == - 1) {
            if (hasZero(indexes)) {
                LCS[i] = 0;
            } else if (equal(indexes)) {
                LCS[i] = LCS[i - sumDistances] + 1;
            } else {
                LCS[i] = longest(i);
            }
        }
        nextIndex(indexes);
    }
}

int main(int argc, char** argv) {

    cin >> N;
    distances = new int[N];
    cellsNum = 1;
    for (int i = 0; i < N; i++) {
        string s;
        cin >> s;
        s = " " + s;
        A.push_back(s);
        L.push_back(s.size());
        cellsNum *= s.size();
    }

    int distance = 1;
    sumDistances = 0;
    for (int i = N - 1; i >= 0; i--) {
        distances[i] = distance;
        sumDistances += distance;
        distance *= L[i];
    }

    LCS = new int[cellsNum];

    for (int i = 0; i < cellsNum; i++) {
        LCS[i] = -1;
    }

    computeLCS();

    printf("%d", LCS[cellsNum - 1]);

    return 0;
}

Noo wykodziłem dzisiaj to :P
Na wejściu jest liczba napisów, a potem tyle napisów. Na wyjściu jest dlugość LCS. Jak wrócę do domu to zrobię wypisywanie LCSów :)

Pozostało 580 znaków

2010-08-28 13:25

Rejestracja: 15 lat temu

Ostatnio: 1 minuta temu

0

No w końcu mi się zachciało i jest pełny algorytm (finezyjny może i nie jest, ale spełnia swoje zadanie):


/*
 * File:   main.cpp
 * Author: Piotrek
 *
 * Created on 27 sierpień 2010, 17:52
 *
 * Algorithm for computing LCS.
 *
 * Input:
 * - number of input strings,
 * - input strings in separate lines,
 *
 * Output:
 * - length of LCS,
 * - one of possible LCSes,
 */

#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <string>
#include <vector>

using namespace std;

// input strings with attached " " (which do not count for LCS but simplify things)
vector<string> A;
// lengths of input strings with attached " "
vector<int> L;
// emulating multi-dimensional array with one-dimenstional
int *LCS;
// total size of above array
int cellsNum;
// distance[i] tells how much we should move in emulated array if we want to increment/ decrement index in dimension i
int *distances;
// sum of above array - tells how much we should move if we want to increment/ decrement all indexes at once
int sumDistances;
// number of input strings
int N;
// length of LCS
int lcsLength;
// one of possibles LCSes
char* lcsString;

bool hasZero(int *indexes) {
    bool result = false;
    for (int i = 0; (!result) && (i < N); i++) {
        result |= indexes[i] == 0;
    }
    return result;
}

bool equal(int *indexes) {
    bool result = true;
    for (int i = 1; result && (i < N); i++) {
        result &= A[i - 1][indexes[i - 1]] == A[i][indexes[i]];
    }
    return result;
}

int longest(int index) {
    int result = 0;
    for (int i = 0; i < N; i++) {
        if (LCS[index - distances[i]] > result) {
            result = LCS[index - distances[i]];
        }
    }
    return result;
}

int computeLongestIndex(int index) {
    int result = 0;
    int longest = 0;
    for (int i = 0; i < N; i++) {
        if (LCS[index - distances[i]] > longest) {
            longest = LCS[index - distances[i]];
            result = i;
        }
    }
    return result;
}

void nextIndex(int *indexes) {
    for (int i = N - 1; i >= 0; i--) {
        indexes[i]++;
        if (indexes[i] == L[i]) {
            indexes[i] = 0;
        } else {
            break;
        }
    }
}

void computeLCS() {
    int *indexes = new int[N];
    for (int i = 0; i < N; i++) {
        indexes[i] = 0;
    }
    for (int i = 0; i < cellsNum; i++) {
        if (LCS[i] == - 1) {
            if (hasZero(indexes)) {
                LCS[i] = 0;
            } else if (equal(indexes)) {
                LCS[i] = LCS[i - sumDistances] + 1;
            } else {
                LCS[i] = longest(i);
            }
        }
        nextIndex(indexes);
    }
}

void traceLCS() {
    int *indexes = new int[N];
    int index = cellsNum - 1;
    for (int i = 0; i < N; i++) {
        indexes[i] = L[i] - 1;
    }
    for (int charsLeft = lcsLength; charsLeft > 0; charsLeft--) {
        while (!equal(indexes)) {
            int longestIndex = computeLongestIndex(index);
            indexes[longestIndex]--;
            index -= distances[longestIndex];
        }
        lcsString[charsLeft - 1] = A[0][indexes[0]];
        for (int i = 0; i < N; i++) {
            indexes[i]--;
        }
        index -= sumDistances;
    }
}

int main(int argc, char** argv) {

    cin >> N;
    cin.ignore();
    distances = new int[N];
    cellsNum = 1;
    for (int i = 0; i < N; i++) {
        string s;
        getline(cin, s);
        s = " " + s;
        A.push_back(s);
        L.push_back(s.size());
        cellsNum *= s.size();
    }

    int distance = 1;
    sumDistances = 0;
    for (int i = N - 1; i >= 0; i--) {
        distances[i] = distance;
        sumDistances += distance;
        distance *= L[i];
    }

    LCS = new int[cellsNum];

    for (int i = 0; i < cellsNum; i++) {
        LCS[i] = -1;
    }

    computeLCS();

    lcsLength = LCS[cellsNum - 1];
    lcsString = new char[lcsLength + 1];
    lcsString[lcsLength] = 0;

    cout << lcsLength << endl;

    traceLCS();

    cout << lcsString << endl;

    return 0;
}

Poprzedni post można skasować.


"Programs must be written for people to read, and only incidentally for machines to execute." - Abelson & Sussman, SICP, preface to the first edition
"Ci, co najbardziej pragną planować życie społeczne, gdyby im na to pozwolić, staliby się w najwyższym stopniu niebezpieczni i nietolerancyjni wobec planów życiowych innych ludzi. Często, tchnącego dobrocią i oddanego jakiejś sprawie idealistę, dzieli od fanatyka tylko mały krok."
Demokracja jest fajna, dopóki wygrywa twoja ulubiona partia.

Pozostało 580 znaków

2010-08-28 18:01

Rejestracja: 12 lat temu

Ostatnio: 3 lata temu

0

Wielkie dzięki. Przeanalizuję sobie kod aby go zrozumieć :D

EDIT: Czy Twoje rozwiązanie będzie złożoność obliczeniową O(k1k2...*km) ?
k1.. k2 - to długości poszczególnych ciągów
m - ilość ciągów wejściowych.

Pozostało 580 znaków

donkey
2010-08-28 22:29
donkey
0

Nie. Złożoność jest taka jak na wiki:
user image

Pozostało 580 znaków

2010-09-08 08:56

Rejestracja: 12 lat temu

Ostatnio: 3 lata temu

0

Przeanalizowałem sobie trochę twój kod i nasuwa mi się jedna myśl. Mianowicie będzie on miał ogromne zużycie pamięci, przykładowo dla 5 ciągów o przypadkowych długościach :

3, 5, 6, 9, 3

Rozmiar tablicy LCS wyniesie :

3 x 5 x 6 x 9 x 3 = 2430 bajtów

A to tylko dla 5 ciągów, w zadaniu mam napisane że algorytm ma działać z maksymalną liczbą 1000 ciągów. Wtedy pewnie ilość będzie już liczona w GB :D Tak więc poszperałem trochę w internecie, znalazłem stronkę ze zoptymalizowanym algorytmem http://edu.i-lo.tarnow.pl/inf/alg/001_search/0055.php w niższej części strony jest podana zoptymalizowana wersja która wymaga zdecydowanie mniejszej ilości pamięci. Co o tym sądzisz ?

Pozostało 580 znaków

Odpowiedz

1 użytkowników online, w tym zalogowanych: 0, gości: 1, botów: 0