Witam!
Czy spotkał się ktoś z Was z algorytmem który wyszukiwałby podobne bloki tekstu w jednym duzym tekście?
Coś co pozwoliłoby na określenie jakiejś struktury dokumentu. Uczenia się tej struktury.
Jeżeli ktoś z Was natknął się na taki lub podobny algorytm lub wie z jakimi zagadnieniami (jakieś sieci(?) itp.) proszę o wskazówki.
Z góry dziękuję za pomoc.
chodzi ci o to zeby najpierw zbieral skrawki tekstu pozniej je dodawal do tablicy a poznie jje wyszukiwal
Chodzi mi o to np. mam dokument HTML
<html>
<body>
<h1 class="tyt">tytul 1</h1>
<p class="styl">jakis tekst</p>
<h1 class="tyt">tytul 2</h1>
<p class="styl">jakis tekst2</p>
<h1 class="tyt">tytul 3</h1>
<p class="styl">jakis tekst3</p>
<h1 class="tyt">tytul 4</h1>
<p class="styl">jakis tekst4</p>
<h2>przyklady</h2>
<table>
<tr><th>fdddgdfg</th>
...
</table>
</body>
</html>
i chciałbym aby algorytm wyszukał podobne bloki tekstu, czyli w tym przypadku od
Zdaje sobie sprawe ze jest to trudne zagadnienie. Dodam tylko że tych znaczników htmlowych w powtarzających się blokach bedzie o wiele wiecej.
to nie jest trudne
to jest podstawowe zagadnienie i nie jest to w zadnym stopniu skomplikowane jezeli cie dobrze zrozumialem
po pierwsze chcialbym sie dowiedziec w jakim jezyku chcesz to miec
szukasz ciagu znakow <h1 pozniej szukasz znaku /p
pozniej znowu szukasz ciagu znakow <h1 pozniej szukasz znaku /p
i znowu szukasz ciagu znakow <h1 pozniej szukasz znaku /p
az do tego momentu kiedy dojdziesz do konca dokumentu i nie bedzie juz <h1
to jest kilka instrukcji warunkowych if nic specjalnego
@up LOL w ogóle nie zrozumiałeś problemu ;]
Problem jest złożony i raczej nie trafisz na gotowe rozwiązanie. Samo szukanie wzorca w tekście to już ciekawe i skomplikowane zagadnienie (istnieje na to kilka gotowych algorytmów). Ale ty chcesz jeszcze ten "wzorzec" znaleźć, co komplikuje sprawę.
Zauważ dodatkowo że to co dla ciebie jest "podobnym" fragmentem tekstu, dla komputera nijak nim nie jest. Podobne są tylko znaczniki html i na nich bym się skupił. Jedyne co mi przychodzi na myśl to jakieś kombinowanie z regexpami.
To zadanie ma bardzo proste rozwiązanie w czasie O(N^4).
Dla każdego spójnego fragmentu wejścia X o długości l
Dla każdego spójnego fragmentu wejścia Y o długości l (X <> Y)
Jeżeli odległość Hamminga(X,Y) < PRÓG to znaleziono parę X,Y
PRÓG-może zależeń od l, np. l/5
X-ów jest O(N^2)
Y-ów dla każdego X jest O(N)
Obliczenie odległości to O(N)
Jestem przekonany, że można z tym algorytmem zejść do O(N^3). Myślę o programowaniu dynamicznym.
Odpada. Przecież ciągi mogą mieć różną długość, to raz. Dwa, jak już pisalem, one tak na prawdę nie sa podobne ;] Przykład:
<h2> lalala </h2>
i
<h2> hihihihihihihihihih </h2>
Wg autora to mają być podobne ciągi, a choćby za pomocą odleglosci Hamminga nie są.
i w czym problem z tego tekstu
<h2> lalala </h2>
i
<h2> hihihihihihihihihih </h2>
wyjac
lalala i hihihihihihihihihih
???????????
Jeśli to ma być jakiś XML to można to sparsować do drzewa DOM i potem porównywać kolejnych synów dla każdego węzła. Jeśli dwoje lub więcej kolejnych synów ma taką samą strukturę to są "podobne".
Chyba nie wszyscy rozumieją ten problem.
Powiedzmy, że celem algorytmu jest rozłożenie na czysty(!!) tekst dowolnego bloga, pogrupowanie niektórych rzeczy w paczki (autor artykułu, artykuł, komentarze do artykułu, autorzy tych komentarzy itd.).
Wiadomo że są popularne silniki blogów, ale tez jest troche blogów napisanych własnoręcznie przez ich autorów. Poza tym popularne silniki blogów mają możliwość dołączania przeróżnych pluginów, które zazwyczaj zmieniają trochę HTMLa.
Myślę że problem nie jest taki prosty jak się niektórym wydaje.
To zastanów się czy chcesz rozebrać forum na części, czy znaleźć powtarzające się bloki tekstu, czy może wzorce w kodzie HTML. To trzy różne zagadnienia.
Wydaje mi się że aby rozebrać forum/bloga na części potrzebna jest wiedza na temat jego struktury. Może właśnie poprzez powtarzające się bloki tekstu czy też wzorce HTMLa można określić właśnie jego strukturę. Wydaje mi się to dość powiązane, a ja szukam algorytmów które mogłyby mi w tym pomóc.
To dwa zazębiające się tematy. To co chcesz zrobić można by zamknąć w kanonie Web miningu
Jeśli natomiast tak bardzo chcesz algorytm, który znajdzie powtarzające się wzorce na stronie WWW, to możesz spróbować tego, co ostatnio nie pozwalało mi zasnąć:
Zapisujesz, w dynamicznej tablicy lub na jednokierunkowej liście powiązanej, kolejno przetwarzane tagi, czyli:
HTML => HEAD => /HEAD => BODY ...
Następnie tworzysz słownik (tablicę asocjacyjną), którego indeksem jest zbiór wszystkich tagów dostępnych na stronie lub ogólnie wszystkich tagów HTML. Każda pozycja słownika wskazuje na inny słownik, który posiada na początku pozycję "nodes" => lista węzłów.
Podczas parsowania dokumentu (x)HTML zapisujesz do dynamicznej tablicy / listy powiązanej kolejno przetwarzane tagi, tak jak to pokazałem powyżej. Następnie pozycję (z listy/tablicy) każdego przetwarzanego tagu dodajesz do "nazwa tagu"=>"nodes", tak że w konsekwencji pod "nazwa tagu" => "nodes" masz tablicę wystąpień danego tagu na liście wszystkich przetworzonych już elementów.
W momencie gdy przetwarzasz każdy tag i wrzucasz jego pozycję na listę powiązaną, sprawdzasz też czy gdzieś już ten tag nie wystąpił. Używasz do tego słownika. Jeśli tag wystąpił, to pobierasz wszystkie jego pozycje na liście powiązanej i sprawdzasz czy kolejny przetwarzany tag znajduje się na pozycji n+1, gdzie n to każda z pozycji wystąpienia tagu, który analizowałeś w poprzednim kroku. Jeśli okaże się, że n + 1 został już znaleziony, to dodajesz do słownika "nazwa poprzedniego tagu" => "nazwa aktualnego tagu" => "nodes" => wystąpienia kombinacji: tag poprzedni, tag następny.
W konsekwencji algorytm powinien zbudować, na bazie powiązanych słowników, drzewa tagów wraz z pozycją znaku znajdującego się zaraz za końcem drzewa. Jedyną wadą tego rozwiązania jest, że algorytm nie wie co Ciebie interesuje, więc:
4 wystąpienia H2, P następujące po sobie mogą równie dobrze zostać odebrane jako 2 wystąpienia H2, P, H2, P
Podobnie może być w sytuacji, w której H2, to tytuł notki bloga, P, to treść notki, a A zostaje niekiedy umieszczony zaraz po P jeśli do notki dodano jakieś komentarze. W konsekwencji na stronie może istnieć kilka różnych kombinacji:
H2, P, A oraz H2, P
Co prawda w tym wypadku można by przyjąć "H2, P" jako właściwy element ale przy bardzie skomplikowanych konstrukcjach niewielka część jednej grupy tagów może się powtarzać w zupełnie innym miejscu.
Skoro to ma być jakiś crawler do blogów i innych, może napisz jakiś prosty parser HTML który będzie działać jak prosta przeglądarka. Mam na myśli to że w pamięci nie będziesz miał czystego HTML tylko bloki tekstu tak jak na normalnej stronie. Wtedy tylko wyszukujesz najdłuższe bloki/największe bloki/inne bloki. Moim zdaniem nie zrobisz uniwersalnego crawlera do każdego bloga/strony/itd bez żadnych sieci neuronowych i innych ciekawych rzeczy.