1. Odległość edycyjna , zozol 16/11/05 11:04
   Link:
   http://winnie.ics.agh.edu.pl/...tyka/pjn/lab/lab2/
   
   Generalnie chodzi o to, ze znajduje sie ile minimalnie liter trzeba zamienic, dodac lub usunąć zeby jeden string byl rowny drugiemu. Potem zamienia sie to na procenty. Implementacje sciagnalem z:
   http://www.torry.ru/authorsmore.php?id=4239
   
   Algorytm dziala w czasie O(n*m) - tak na oko nie da się szybciej tego policzyc.
   1. Zakladam, że algorytm porownywania zakładamy, że jest ok. , jenot 16/11/05 11:23
      Ale ty algorytm ogólny źle napisałeś... NIGDY kazdy z kazdym w jednej "dupnej" pętli. To zabójstwo.

      Mój podpis max 100 zanaków,
      zabroniony spam oraz reklama.

   2. Da się któcej, przy paru założeniach: , bwana 16/11/05 11:48
      1. określamy górny limit błędów edycyjnych, który dyskwalifikuje parę ciągów jako ciągi podobne (czyli takie same, tylko z błędem:-D)
      
      Dzięki temu, jeśli w danym wierszu macierzy z algorytmu w żadnej komórce nie mamy już liczby mniejszej niż limit górny błędów, możemy nie przetwarzać dalszych kolumn, bo wiadomo, że lepiej już nie będzie - reszta ciągów może być co najwyżej identyczna, ale przecież początek już sprawdziliśmy - limit jest przekroczony.
      
      Chodzi o to, że nie chcemy w tym zadaniu tak naprawdę sprawdzić, jaka jest odległość edycyjna ciągów, tylko czy odległość ta nie przekracza jakiegoś założonego limitu.
      
      Przy ciągach "ala ma kota" i "kot ma alę" i limicie 3 mamy w tym momencie złożoność O(3 * min(dlugosc1, dlugosc2)) zamiast O(dlugosc1 * dlugosc2)
      
      Ponadto można wyeliminować porównania tych par, dla których różnica w długości ciągów jest większa niż podany limit.
      
      2. Zoptymalizować też można dobieg algorytmu, czyli nie sprawdzać podobieństwa ciągów do końca, tylko do momentu, gdy upewnimy się, że w dalszej (niesprawdzonej jeszcze) części ciągów nie ma szans pojawienie się więcej błędów niż założony limit - najmniejsza dotychczas wykryta liczba błędów edycyjnych. Przykładowo:
      
      "Ala ma kota" i "Ala ma kopa" i limicie 3 mamy:
      
      "Ala ma k" - dotychczas 0 błędów, do końca ciągu (a właściwie dłuższego z ciągów, ale przecież tu mają równą długość) zostały 3 znaki, czyli możemy przerwać sprawdzanie, ciągi są podobne bo już więcej niż 3 (czyli limit) błędy nie mają szans się ujawnić.
      
      Podsumowując: z porównań usuwamy pary ciągów o różnicy w długości większej niż ... a pozostałe pary sprawdzamy tylko do momentu, kiedy albo błędów jest więcej niż ... albo do momentu, kiedy błędów nie pojawi się już na tyle dużo, aby ciągi były uznane za niepodobne.

      "you don't need your smile when I cut
      your throat"

      1. on zyjeee! , Ranx 16/11/05 11:52
         he he he.
         
         i jeszcze korbki mu sie zachcialo :P

         o roztramtajdany charkopryszczańcu...

      2. tak, ale , zozol 16/11/05 12:14
         to ciagle jest tylko facelifting. Masz racje, ze skroci to czas obliczania czesci podobienstw, ale dojdzie dodatkowy czas sprawdzania tych wszystkich warunkow na kazdym kroku
         1. zobaczmy jak to będzie , bwana 16/11/05 12:54
            przede wszystkim zależy to niestety od konkretnych danych, np. od rozkładu dlugosci ciągu w bazie. Wstępna eliminacja na podstawie różnicy długości większej niż limit jest tym korzystniejsza im bardziej długość ciągu w bazie jest zbliżona do rozkładu równomiernego (ale tylko pozornie, o tym zaraz), przykładowo:
            
            1000 ciągów, każdy o tej samej długości to 1000^2 = 1000000 pełnych sprawdzeń, bo nie ma wstępnej eliminacji na podstawie różnicy długości
            
            1000 ciągów, 500 o długości A i 500 o długości B tak, że A-B>limit:
            
            2*500*500=500000 pełnych sprawdzeń
            
            1000 ciągów, 100 różnych klas ciągów (dla danej klasy A ciągów nie istnieje taka klasa B w której długość ciągu z klasy A - limit <= dlugość ciągu klasy B ) daje nam 10*100^2 porównań=100000
            
            1000 ciągów, 100 klas ciągów=100*10^2 = 10000 porównań
            
            Oczywiście należy pamiętać o tym, że każde porównanie pełne ma charakter mniej więcej O(n*m) więc tak naprawdę zależy nam na podziale nierównomiernym, czyli jak najmniejszej liczbie porównań dla par ciągów najdłuższych. Ale możliwość takiego podziału zależy od danych. Tak czy siak, widać, że wprowadzenie wstępnej selekcji na podstawie różnicy długości ciągów może dać zysk.
            
            Jak często sprawdzamy limity w algorytmie "pełnego sprawdzenia"?
            
            Bierzemy dwa ciągi (o różnicy długości nie większej niż limit) i "chodząc" po macierzy liczymy w kolumnach dotychczasową liczbę błędów edycyjnych. Tworzymy zmienną DOTYCHCZASOWE_MINIMUM i utrzymujemy w niej wartość minimalną z dotychczas wstawionych do macierzy. W momencie, gdy wartość DOTYCHCZASOWE_MINIMUM>limit, przerywamy obliczenia, para jest uznana za niepodobną.
            
            Na podobnej zasadzie utrzymujemy zmienną DOTYCHCZASOWE_MAKSIMUM. Jeśli wartość tej zmiennej <= max(dlugosc ciagu pierwszego, dlugosc ciagu drugiego) - numer kolumny którą właśnie sprawdzamy, to ciągi na pewno są podobne, przerywamy obliczenia.
            
            Sprawdzenie pierwsze ma sens dopiero w wierszach od limit+1 do końca macierzy a sprawdzenie drugie w wierszach maks(dlugosc1, dlugosc2) - limit do konca macierzy.
            
            Oba sprawdzenia należy wykonywać po skompletowaniu pełnego wiersza w macierzy.

            "you don't need your smile when I cut
            your throat"

            1. i jeszcze , bwana 16/11/05 13:04
               jeśli ciągi są długie i wiemy skądś (o ile to wiemy, rzecz jasna) że grupy podobnych ciągów mają taką budowę, że jest w nich dużo ciągów identycznych i zaledwie kilka z drobnymi błędami, to wstępną selekcję można też wykonać (oprócz badania różnic w długości)... porównując ciągi. Po prostu. Funkcja strstr (być może już nie pamiętam nazwy) w C czy każda inna napisana w ten sposób jak ma to miejsce w standardzie C działa o wiele szybciej niż miara odległości edycyjnej, więc jeśli identyczność występuje częściej niż podobieństwo, można najpierw sprawdzać właśnie identyczność. Oczywiście zastosowanie tego rozwiązania zależy od tego co wiemy o danych i nie ma charakteru uniwersalnego. Wyglądałoby to tak:
               
               1. Sprawdzamy różnicę w długości (jeśli za duża, ciągi są niepodobne, koniec)
               2. Sprawdzamy identyczność (jeśli identyczne, koniec)
               3. Sprawdzamy podobieństwo (miara edycyjna).
               
               Więcej nie wymyślę;-D

               "you don't need your smile when I cut
               your throat"

            2. małe pytanko , BONUS 16/11/05 13:05
               bo widzę, że znasz podobny problem dogłębnie
               na podstawie przykładu który podał zozol może lepiej byłoby zrobić trójkrokowo:
               - oczyścić dane (zamienić na duże angielskie litery wszystko)
               - pochlastać linie na podciągi (wyrazy) i policzyć pomiędzy nimi przejscia (ponieważ wygląda to na dane dobrze słownikowalne) nadac im mnemoniki
               dopiero mnemoniki porównywać (mająć zasłownikowane przejścia będzie szybciej)
               
               Pozdro
               BONUS
               1. mała odpowiedź:-D , bwana 16/11/05 13:40
                  i tak i nie
                  
                  "ALA MA KOTA"
                  "ALA MA KOŁA"
                  "ALA MA KOPA"
                  "ALA MA KOTA"
                  "ALA KOTA MA"
                  
                  ALA-A
                  MA-B
                  KOTA-C
                  KOŁA-D
                  KOPA-E
                  
                  ABC
                  ABD
                  ABE
                  ABC
                  ACB
                  
                  ABC-ABC - proste, identyczne ciągi i do tego krótkie:-D
                  ABC-ABD - 1 błąd edycyjny równy odległości edycyjnej między C i D (czyli między KOTA i KOŁA), trzeba jednak obliczyć całkowite podobieństwo, bez optymalizacji zw. z limitem między KOTA i KOŁA (i być może zapisać gdzieś "na później", co może być z kolei optymalizacją, że (C-D-1))
                  ABC-ACB - dwa błędy edycyjne, jeden to wstawienie, drugi usunięcie - ich wartość? suma długości wstawianego wyrazu i usuwanego wyrazu? być może, ale jeśli mamy
                  
                  "MAMA MAMY" i "MAMY MAMA" -> AB i BA to znów, wstawienie (4) i usunięcie (4) dające nam 8 błędów edycyjnych, a porównanie bez podziału na mnemoniki daje nam 2 błędy (zastąpienie A literą Y i vice versa) - słowem - dla rzetelności trzeba byłoby sprawdzać odległości edycyjne między ciągami mnemoników i odległości edycyjne "w okolicy" błędów, które wystąpiły, ale to już licząc podobieństwa konkretnych wyrazów odpowiadających mnemonikom. Ale sam zamysł jest godzień dalszego kombinowania.
                  
                  W przypadku "obcowania" z danymi, które mają niewielki słownik wyrazów (mnemoników) możliwe jest np. utrzymanie słownika mnemoników i słownika podobieństw, typu:
                  
                  1.
                  mnemonik-slowo
                  A-ALA
                  B-ELA
                  C-KOTA
                  D-MA
                  E-PSA
                  
                  2.
                  mnemonik-mnemonik-odleglosc edycyjna
                  A-B-1
                  A-C-3
                  
                  i tak dalej

                  "you don't need your smile when I cut
                  your throat"

      3. nawiasem pisząc, artykuł okołotematyczny , bwana 16/11/05 12:25
         http://www.zsi.pwr.wroc.pl/missi2000/referat11.htm
         
         warto zajrzeć do źródeł, przejrzeć materiały Tsenga[11] i Manbera[13], do swojej magisterki korzystałem z nich przy optymalizacji wyszukiwania melodii kluczowych (czyli porównywania podciągów w ramach ciągu - zagadnienie podobne do omawianego w tym wątku). jeśli uda mi się odkopać [10] i znajdę pseudokod mojego algorytmu, postaram się go tu umieścić.

         "you don't need your smile when I cut
         your throat"

Nie ma piekła poza tym światem, on nim
jest, nie ma diabła poza człowiekiem,
on nim jest!

Mój podpis max 100 zanaków,
zabroniony spam oraz reklama.

1. plik nie ma znaczenia , zozol 16/11/05 11:15
   nie wazne co w nim jest, mogą być losowe ciągi znakow
   
   Sama pętla, ktora nic nie robi, tylko skacze po wszystkich parach numerów linii:
   
   for i:=0 to 120000 do
   for j:=0 to 120000 do;
   
   wykonuje się na moim kompie 30 sekund. Teraz sobie wyobraź, że wstawiamy w środek dosyć złożoną operację sprawdzania podobieństwa stringów (o wiele bardziej skomplikowaną obliczeniowo od obsługi samej pętli) - wg mnie to oczywiste, ze bedzie to dlugo trwac
   1. No właśnie tak podejrzewałem. , jenot 16/11/05 11:20
      Na dzieńdobry źle .. Takich rzeczy tak się nie robi ...
      Musisz najpierw przygotować jakieś grupy danych.
      A potem pracować na wielu mniejszych grupach.
      Przecież można wyselekcjonować na dzień dobry stringi długie / krótkie.
      I już wtedy masz
      
      for i:=0 to 60000 do
      for j:=0 to 60000 do
      blbla grupy1 ;
      
      for i:=0 to 60000 do
      for j:=0 to 60000 do
      blbla grupy1 ;
      
      
      A to już wykona się 2 razy szybciej.

      Mój podpis max 100 zanaków,
      zabroniony spam oraz reklama.

   2. A jak uda Ci się takich grup wyselekcjonować więcej , jenot 16/11/05 11:21
      i precyzyjniej to program może nawet w kilkanaście minut to przeliczy.

      Mój podpis max 100 zanaków,
      zabroniony spam oraz reklama.

      1. Nie można tego podzielić na zadne grupy , zozol 16/11/05 11:30
         Nie ma stringow dlugich/krotkich - problem wymaga tego, zeby porownywac kazdy z kazdym.
         
         Moze byc jeden string dlugosci 200, drugi 250 - jesli ten 200 bedzie podstringiem tego 250, to mamy podobienstwo 80% - gdybys ustawił swoją granicę na 225 znakow, to nigdy bys nie znalazl tego podobienstwa.
         
         Zresztą tak jak juz pisalem - potrzebne by bylo przyspieszenie dwoch rzedow wielkosci, a tego sie nie osiagnie takimi optymalizacjami "na szybko"
         1. Poprostu nie wierzę, że nie da się zrobić wstępnej kwalifikacji. , jenot 16/11/05 11:41
            Nie ma takich danych, których nie da się pogrupwać i na dzieńdobry podzielić.
            
            Chyba, że są takie same.

            Mój podpis max 100 zanaków,
            zabroniony spam oraz reklama.

         2. Był kiedyś konkurs Eternity puzzle , jenot 16/11/05 11:53
            209 klocków - każdy inny.
            
            ilość kombinacji:
            209! 12^209 = 1.78 x 10^621 =
            17833793934355021599464216158237055788952960455559
            39664896828810374848966374425926802848828727014922
            61315990512949829112824604442584684546438771083512
            57522295775962865471757143571136280296815169246798
            45693750081703198771035364248258740024533100467224
            05456654075512366028886554451498575385935026198748
            07077399743889281160970816002686003875771569106593
            01735277688365076643732669480438110916866047044038
            03926867875412469936614920088622123227132052495512
            49471597235436985731148744631608948167694584536105
            38446606237915444069558620656688440162999906372899
            03387908414394356203520000000000000000000000000000
            0000000000000000000000
            
            http://www.globalwebsuites.com/...rge/eternity.jpg
            
            rozwiązanie: http://alpha.ujep.cz/...her/puzzle/images/pet3.gif
            
            Na dzieńdobry wychodziło, że najlepsze komputery będą to liczyć miliony lat. A jednak przeliczyli to w ciągu 2 lat. Także w optymalizacji siła.

            Mój podpis max 100 zanaków,
            zabroniony spam oraz reklama.

   3. i już tu widać , BONUS 16/11/05 11:30
      że trzeba pomyśleć
      bo jeśli już to
      for i=0 to 120000 do
      for j=i to 120000 do
      ...
      według twojego jest ~14 400 mln porównań 7 200 mln porównań czyli o połowę mniej (z 250 zrobiło się 125 dni :)
      Pozdro
      BONUS
      
      
      po co porównywać w przód i w tył?
      1. jasne ze tak, ale... , zozol 16/11/05 11:33
         to i tak nie rozwiazuje problemu
         1. fajnie , BONUS 16/11/05 11:43
            :)
            kontynuując:
            jak brakuje "żelaza" znaczy się mocy komputerów - trzeba wziąć się za myślenie, i tu rodzą się pytania:
            jak brudne masz dane ? czyli czy większość błędów to literówki, czy też jest to np ten sam tekst w 3 egzemplarzach tylko różnie poformatowany (+ możliwe literówki) i pocięty na wiersze
            czy potrzebne Ci są białe znaki, polskie znaki, duże/małe litery?
            bo może szybciej będzie najpierw oczyścić dane (to jest wyciąć białe znaki , polskie , tylko duże litery - policzyć jakąś funkcją hashującą dla nich skróty i wyciągnąć te linie co są jednakowe i do dalszych porównań zostawić resztę? - jak bardzo zmniejszy Ci się wtedy liczba danych wejściowych?)
            
            Pozdro
            BONUS

   4. Musisz optymalizować ilość porównań a nie algorytm porównujący. , jenot 16/11/05 11:31
      A tutaj myślę, że jest spore pole do optymalizacji. Daltego prosiłem o kilka przykładowych linii. Lubię takie problemiki więc chętnie pomogę.

      Mój podpis max 100 zanaków,
      zabroniony spam oraz reklama.

Mój podpis max 100 zanaków,
zabroniony spam oraz reklama.

1. nie powinno byc problemu z podzialem na wątki , zozol 16/11/05 11:23
   kazdy watek moze sie zająć swoim podzbiorem stringow (np. pierwszy watek wezmie pierwszy tysiac stringow i bedzie liczyl podobienstwo kazdego z nich ze wszystkimi 120 tysiacami, drugi watek - drugi tysiac...)
   
   Zlozonosci problemu sie nie przeskoczy - nie widze mozliwosci obliczenia podobienstwa stringow w czasie krotszym niz O(n*m). Mozna pomyslec jedynie nad optymalizowaniem samej implementacji, ale nie liczylbym na to, ze przyniesie to przyspieszenie dwoch rzędow wielkosci.
   1. Myślę, że przyniesie nawety 10 rzędów wielkości. , jenot 16/11/05 11:34
      Tak jak pisałem wyżej.
      Tylko musisz optymalizować swój algorytm a nie porównujący.

      Mój podpis max 100 zanaków,
      zabroniony spam oraz reklama.

   2. no 10 to przesada :-) , jenot 16/11/05 11:35
      ... Ale czas końcowy do kilkunastu minut / kilku godzin się skróci.

      Mój podpis max 100 zanaków,
      zabroniony spam oraz reklama.

Leave me alone I know what I'm doing!

1. Ja tez. , Mms 16/11/05 14:24
   j.w.

   Pozdrawiam

Linux

Mój podpis max 100 zanaków,
zabroniony spam oraz reklama.

Mój podpis max 100 zanaków,
zabroniony spam oraz reklama.

1. ale o czym Ty piszesz? , zozol 16/11/05 12:06
   zdanie "Także stary nie pisz mi, że się nie da " zabrzmiało, jakbyś przed chwilą podał dowód, że się da. A tego nie zrobiłeś.
   Chyba, że nawiązujesz do tych baz danych z milionami rekordów, które nie mają z tym problemem nic wspólnego. Nie widziałem jeszcze żeby ktoś porównywał wszystkie transakcje kazdy-z-kazdym, a gdyby to robił to by sie nie doczekał wyniku.
   1. Nie będę się kłócił.. Nie chcesz pomocy to nie ! , jenot 16/11/05 12:35
      ... licz sobie to swoje 12k kwadrat skoro to taki dobry algorytm i nie zawracaj ludziom głowy.

      Mój podpis max 100 zanaków,
      zabroniony spam oraz reklama.

      1. Ale kto sie kloci? , zozol 16/11/05 13:13
         Chcialem tylko zrozumiec, dlaczego napisales "Także stary nie pisz mi, że się nie da" - bo to zdanie wydało mi się lekko pozbawione sensu (tak jak pisalem, mialoby sens gdybys podał dowód na to, ze sie da ten problem rozwiazac w "kilka godzin")

   2. Chłopie nie myślisz , jenot 16/11/05 12:45
      Ale SYNEK WEŹ PODZIEL TO KURDE NA TE GRUPY
      nawet bez zadnej klasyfikacji !!!
      
      np 200 grup po 600 wierszy każda i w ich
      obrębie zapuść swój algorytm. To wykona się błyskawicznie.
      bo to w sumie tylko 18000 porównań na grupę.
      
      Po tym już wyjściowa ilość danych będzie mniejsza.
      Potem skleić wyniki pomieszać dane i jeszcze raz.
      i tak kilka razy ...
      
      MYŚLEĆ CZŁOWIEKU MYŚLEĆ !!!

      Mój podpis max 100 zanaków,
      zabroniony spam oraz reklama.

      1. to wg mnie tez nic nie da , zozol 16/11/05 13:15
         i tak w koncu bedziesz musial to połączyć i bedziesz mial plik z okolo 50 tysiacami linii, ktory tez bedzie sie liczyl długo, a wczesniej poswiecisz kupe czasu zeby do tego dojsc
         1. nie!!! , beef 16/11/05 13:44
            bo usuniesz już duplikaty!!! zostanie Ci mniej danych. Potem znowu możesz podzielić dzielisz na grupy przecież i kontynuwac ten algorytm!!, kto ci kaze zostać z "plikiem z okolo 50 tysiacami linii, ktory tez bedzie sie liczyl długo"? Jeszce raz dzielisz i usuwasz duplikaty i tak dalej :) Wcześniej tylko dokonaj przemieszania tak, żeby nie porównywać znowu tych samych ciągów, dlatego najlepiej podzielić na n grup po n ciągów, lub blisko takiego podziału. Po pierwszej eliminacji ustawiasz ciągi tak: pierwszy z pierwszej grupy, pierwszy z drugiej, pierwszy z trzeciej,...., drugi z pierwszej, drugi z drugiej itd. Klasyczny algorytm "dziel i rządź" z decymacją :)

            this is the time of the revolution
            keepin' it in the right track
            feelin' it in my mind back

            1. nie!!! , zozol 16/11/05 13:58
               przeciez w koncu ma pozostac jakies 40-50 tysiecy linii, bo tyle jest unikatowych wpisow - nawet jesli wstepne etapy zredukują liczbe z 120 tysiecy do okolo 50 tysiecy, to w koncu i tak bedziesz musial kazdy z tych 50 tysiecy porownac z kazdym, nie wazne czy bedziesz sobie dzielił na grupy czy nie.
               1. powiedz.. , beef 16/11/05 14:07
                  ..szczerze - Ty nie chcesz sobie dać pomóc, prawda? Jeśli ze 120 tys zostanie 50, a Ty twierdzisz, że przy algorytmie n^2 nie da to znaczącego przyrostu, to nie wiem, co można więcej napisać.

                  this is the time of the revolution
                  keepin' it in the right track
                  feelin' it in my mind back

                  1. a gdzie napisalem , zozol 16/11/05 14:55
                     ze nie da znaczacego przyrostu? da przyrost, ale nie wystarczajacy

            2. więc uściślę jeszcze.. , beef 16/11/05 14:34
               ..powtarzasz algorytm na grupach k razy (k dobrane dośw. albo "na oko") oraz do czasu, gdy kolejna iteracja daje jeszcze eliminację większą niż ileśtam. Jeśli >k lub brak dużej eliminacji, przerywasz i sprawdzasz to, co zostało. Powiedzmy, masz 350 grup po 350
               50 000*50 000 = 2 500 000 000
               120 000*120 000= 14 400 000 000
               Prawie sześciokrotna redukcja czasu obliczeń ostatniej fazy
               k * 120 000 * 350 = k * 42 000 000 (k faz wstępnych)
               Musiałbyś mieć k około 300, żeby mieć tyle samo porównań! Jeśli jednakowe wpisy znajdują się blisko siebie, to jest duża szansa że po 2 iteracjach wyczyścisz już dobrze. Nie dowiesz się tego, zanim nie zaimplementujesz i sprawdzisz.

               this is the time of the revolution
               keepin' it in the right track
               feelin' it in my mind back

               1. problem w tym , zozol 16/11/05 15:01
                  ze nawet gdyby miec 6 krotne przyspieszenie tej ostatniej fazy (nie liczac juz czasu straconego na poprzednie fazy) to nadal jest to sporo czasu - ciagle zbyt duzo, zeby zapuszczac to na zwyklym kompie. Dlatego od poczatku uwazam, ze najlepszym sposobem bedzie rozproszenie tego na wiele kompow
                  1. guzik prawda... , xmac 16/11/05 15:34
                     nie masz racji, bo zdecydowanie bardziej zlozone operacje na wiekszej porcji danych wykonuje sie na pojedynczych maszynach
                     wiem to, bo zajmowalem sie troche czyszczeniem danych, ktorego jednym z etapow jest tzw. deduplikacja

                     dual&mobile power
                     XMAC

         2. Jeśli szukasz gotowego programu co to zrobi w 10 minut to możesz mieć problem. , jenot 16/11/05 15:25
            Jak sam tego nie zrobisz to samo się nie zrobi ...
            Na tym polega optymalizacja, że w nie jednym a w wielu krokach zamiast algorytmu liczącego 250dni otzymujemy taki, który liczy 2 dni.
            
            W tym poscie otrzymałeć caonajmniej 4 bardzo cenne wskazówki. Użyj ich jak to wszystko z głową połączycz to na 100% uzyskasz satysfakcjonujące wyniki.
            
            Te uwagi to:
            
            1. sugestie kolegi bwama
            2. nie stosować dwukrotnego porównywania ych samych ciągów tylko w dwie strony czyli pętle mają wyglać zamiast:
            for i:=0 to ILOSC_WIERSZY do
            for j:=0 to ILOSC_WIERSZY do ;
            następująco:
            for i:=0 to ILOSC_WIERSZY do
            for j:=i to ILOSC_WIERSZY do ;
            3. Zrobić wstępne przygotowanie danych TRIM'y, ewentualne uzunięcie spacji przecinków lub innych znaków jeśli nie są istotne dla treści (oczywiście wcześniej poindeksować wiersze, żeby mieć możliwość wskazania oryginału)
            4.Można zastosować słowniki (polecam ispell) - to skróci pracy procedury porównującej
            5. kilka innych ...
            
            
            Ale mój wniosek z Twoich odpowiedzi jest jeden. Nie czytasz tego co Ci tutaj piszą,
            szukasz cudownego i nieistniejącego środka na rozwiązanie tego problemu.
            Jak byś poświęcił cały czas (te kilka godzin), na implementacje algorytmu zamiast szukanie klastrów obliczniowych itp..., z którymi sobie i tak nie poradzisz bo widzę, że programowania we krwi to nie masz i przygotowanie dobrego wielowątkowego sieciowo synchronizującego się programu raczej Cię przerośnie. .... to już byś miał program, który to obliczy w max 5 dni. Czyli Twój cel by został osiągnięty, zadanie zakończone. A tak to w te 250 dni to nawet tego klastra nie znajdziesz.
            
            W takim razie chyba tutaj pomocy nie znajdziesz ...

            Mój podpis max 100 zanaków,
            zabroniony spam oraz reklama.

            1. uwielbiam Twoje wnioski wyssane z palca , zozol 16/11/05 15:47
               dlaczego myslisz, ze szukam "gotowego programu, ktory to zrobi w 10 minut"?
               dlaczego myslisz, ze szukam "cudownego i nieistniejącego środka na rozwiązanie tego problemu"
               
               Dobrze wiem, ze mozna zastosowac pewne optymalizacje, ale jednoczesnie widze (i moge sie o to zalozyc) ze nie dadzą one przyspieszenia 10 krotnego, a mi i tak potrzebne jest raczej 20, a najlepiej 100 krotne.
               
               A jesli piszesz o "wielowątkowym sieciowo synchronizującym się programie" to pokazujesz tylko jak mało o tym pomyślałeś. Ten problem nie wymaga zadnej synchronizacji miedzy wątkami - obliczenia w jednym wątku nie potrzebują danych z innych wątków.
               1. dobra sam wszystko wiesz lepiej.. , jenot 16/11/05 17:07
                  Tylko szkoda, że nie umiesz tego samodzielnie zrobić.

                  Mój podpis max 100 zanaków,
                  zabroniony spam oraz reklama.

                  1. na tym przeciez polega dyskusja... , zozol 16/11/05 17:19
                     ze kazdy wyraza swoje zdanie - nie musisz sie od razu obrazac jesli ktos wytyka Twoje bledy
                     1. tja , BONUS 16/11/05 23:43
                        dyskusja polega na tym że obie strony przedstawiają jakieś argumenty, a TY, bez urazy, wyglądasz jakbyś nie chciał dać sobie pomóc, tylko moc obliczeniowa i moc obliczniowa - klapki na oczy i wszystko metodą czołgową, na uraaaaaaaaaaaaaaaaa
                        Rozumiem, że gdyby dane wejściowe były generowane losowo to wszystkie metody "inteligenrniejsze" były by słabsze, ale według przykładu dane nie są losowe. Sądze że dało by się zesłownikować je w 10-15 tys słow. wstawiłbym tabele słowo - wartość wstawienia, oraz drugą słowo-słowo - wartość przejścia
                        poza tym zrobić dla każdego wiersza indeks bitowy mówiący że dany wyraz słownikowy wystąpił porównanie takich indeksów bitowych jest błyskawiczene i jeżeli zgodność jest na poziomie np 15 słow na 20 to jest bardzo duża szansa że jest to to samo warto wedy babrać się w dokładne porównanie
                        dla reszty wierszy liczyć koszty przejścia (mająć już słownik z policonymi kosztami jednostkowymi )
                        sądzę że na PIV 1,7GHz 512MB ram +db2+java byłbym w stanie to zrobić w mniej niż 12 godzin
                        
                        Pozdro
                        BONUS
                        1. że pozwolę sobie wtrącić dla dobra postronnych... , XTC 17/11/05 08:15
                           faktycznie tak to wygląda a następujacej dyskusji aż biją po oczach następujące rzeczy które ktoś mógłby jeszcze pomyśleć, że prawidziwe:
                           1) problem jest unikatowy - i nikt go jeszcze nie przerabiał - mało tego - nikt nawet nie zastanawiał się nad podobnymi problemami
                           2) 120 tys linii tekstu do "nieskończenie wiele"
                           3) dzisiejsze kompy nie powinny być w stanie nawet sprawdzać pisowni na bieżąco ponieważ doprowadziłoby to do totalnego crash'u.

                           Linux

                           1. Masz rację! , BONUS 17/11/05 08:47
                              małe wytłumaczenie
                              1. masz rację - nie jestem informatykiem - na pewno ktoś już coś takiego przerabiał (z resztą cytowane wcześniej miary to potwierdzają)
                              2. masz rację :) (sprawdziłem przeparsowanie zbioru 1,8mln lini ze znalezieniem słów kluczowych i odpytaniem bazy oraz odpowiednim zapisem do bazy wyników robione w javie przeze mnie (na kolanie) na słabym sprzęcie trwa 40 min)
                              3. BARDZO PRZEPRASZAM &#8211; jest mi wstyd, na swoje usprawiedliwienie dodam, że pisałem bardzo późno i po ciemku (córka spała)
                              
                              Pozdro
                              BONUS
                              1. oj przestań... , XTC 17/11/05 09:18
                                 jestem ostatnią osobą która czepiałaby się literówek - w sytuacji gdy sama robi masę błędów ...
                                 aż mi trochę wstyd, że tak mogłeś to odebrać :(
                                 boo...
                                 podałem to tylko jako przykład wydajności dzisiejszych komputerów.

                                 Linux

1. ech , beef 16/11/05 15:54
   "wytnie to mniej niz polowe porownan, a doda porownywanie dlugosci.". Przecież jeśli przetablicujesz sobie wstępnie długości ciągów, to porównanie długości to porównanie jednego int-a, a porównanie stringów to... sam wiesz. I co, nadal twierdzisz, że się nie opłaca?

   this is the time of the revolution
   keepin' it in the right track
   feelin' it in my mind back

2. dodaj te wszystkie optymalizacje do siebie , beef 16/11/05 15:55
   a 20 krotny przyrost szybkości masz w zasięgu ręki. Zresztą - jak chcesz :)

   this is the time of the revolution
   keepin' it in the right track
   feelin' it in my mind back

-
WoojO

1. a mozesz podac jaki masz na mysli? , zozol 16/11/05 13:17
   jakie są te specjalne algorytmy? chetnie poznam lepszy - chodzi tylko o to, zeby jakosc zwracanych wynikow byla podobna (tzn. znajdywal podobienstwo miedzy takimi stringami jak w przykladzie)
   1. moja praca... , WoojO 16/11/05 13:29
      .. polegala kiedys na znalezieniu algorytmu porownawczego dla malych stringow. I z tego co pamietam (troszke to juz bylo) algortym np. MCWPA byl lepszy niz Leve. Natomiast do duzych to juz troszke zaczyna sie kosmos z tego wzgledu ze czasami wykozystywane byly szeregi fouriera. Algorytmu niestetety nie wskaze :/. Niepamietam. Przejrzalem stos pdf'ow z google i w kazdym bylo cos innego :).

      -
      WoojO

      1. a co to znaczy "duzych"? , zozol 16/11/05 13:33
         od ilu znakow string jest duzy?
         1. duzy... , WoojO 16/11/05 22:17
            ... to znaczy to ze podajesz na wejscie 300 stron tekstu, a na koncu wypluwa ci wynik... ;) poprostu dziala wszystko w ujeciu globalnym. Maly string to naprzyklad samo nazwisko lub miejscowosc.

            -
            WoojO

2. potwierdzam... , xmac 16/11/05 14:23
   levenstein jest czesto wykorzystywany do porownania wyrazow (nie dlugich stringow) i raczej sie sprawdza, chociaz w jezyku polskim jednymi z lepszych sa algorytmy zamieniajace string na zapis fonetyczny
   na pocieszenie dodam, ze aplikacje do czyszczenia danych kosztuja tyyyyyyyyle kasy i stosuja przerozne algorytmy (sieci neuronowe, itd...)
   na pewno da sie czas przetworzenia tych danych skrocic do takiego, ktory bedzie sensowny dla twojej maszymy
   polecam zastanowienie sie nad zastosowaniem algorytmu uwzgledniajacego wersje fonetyczna, algorytm levensteina i funkcje liczaca ilosc przestawien potrzebnych do uzyskania tego samego wyrazu, jesli sklada sie z tych samych liter. jak to dobrze s-cache-ujesz i odopwiednio dobierzesz wagi, to powinno zadzialac dobrze dla wiekszosci danych. niestety z tego co wiem, to nie ma ogolnie dostepnego algorytmu typu soundex (fonetycznego) dla jezyka polskiego (maja go firmy, ale to na wlasny uzytek i nikt ci go nie da). przede wszystkim pamietaj, ze maszyna powinna miec sporo ramu, bo warto zapamietywac to, co raz sie wyliczy. odnalezienie tego w pamieci bedzie duzo szybsze niz wyliczenie na nowo, a powtorzen bedzie sporo
   bardzo wazne bedzie tez odpowiednie przechowywanie danych (w zadnym wypadku nie tablice), zeby szybko je przeszukiwac. w zaleznosci od formatu danych i sposobu zapisu trzeba dobrac odpowiednia strukture
   jak widzisz temat jest bardzo szeroki, ale doswiadczenie zdobyte przy takim projekcie moze okazac sie bardzo cenne!

   dual&mobile power
   XMAC

"you don't need your smile when I cut
your throat"

SM-S908

1. luzik , beef 16/11/05 14:20
   to właśnie jest w tym najfajniejsze :D

   this is the time of the revolution
   keepin' it in the right track
   feelin' it in my mind back

   1. byc czy nie byc? , Ranx 16/11/05 14:22
      :)))

      o roztramtajdany charkopryszczańcu...

      1. najfajniejsze... , beef 16/11/05 15:36
         ...jest zastanawianie się nad rzeczami takimi jak w tym wątku, czyli "być" :)

         this is the time of the revolution
         keepin' it in the right track
         feelin' it in my mind back

2. to ty nie wiesz , Maners 16/11/05 16:29
   jacy tepi potrafia byc "programisci". Np u mnie w pracy to jest wrecz zenada - ludzie z 5-6 letnim doswiadczeniem pisza skrypty w asp bez uzycia jakichkolwiek funkcji czy wykrywaniu bledow. Skrytpy ktore mozna zredukowac do np 15-20 linijek ( jesli sie odpowiednio przemysli zanim zacznie sie cokolwiek klepac) zwykle zajmuja ok 300-400 lini poprzeplatanych tonami petli i if-ow. Ja sam dopiero mam za soba ok 10 miesiecy praktycznego programowania i juz wiekszosc projektow do mnie daja bo jestem je w stanie zrobic w duzo krotszym czasie. Takie problemy jak tutaj zozol zapodal rozwiazuja raczej programisci ktorym sie placi ok 100 - 120$ tys rocznie. Reszta "programistow" zarabiajacych 40-55$ tys (a to juz jest troche) to raczej osoby dla ktorych zagniezdzenie 10 petli, a w nich ze 100 instrukcji warunkowych jest norma i sie nawet nie wysilaja aby pomyslec czy da sie to jakos lepiej zorganizowac.
   1. ja pamietam za czasow , kubazzz 16/11/05 16:53
      szkolnych to mnie krecilo programowanie. Opanowalem Pascala potem troche C i probowalem podstawy assemblera, ale szybko odkrylem ze w sumie bardziej od znajomosci skladni jezyka liczy sie umiejetnosc zrobienia dobrego algorytmu. Pamietam jaka radosc mialem jak udalo mi sie dokonac optymalizacji - czasem program to bylo kilka zrobionych przeze mnie funkcji i procedur, a potem 30 linijek miedzy "begin" i "end". Potem cos mi sie stalo z glowa i nie mam juz wiecej cierpliwosci do zadnych zadan wymagajacych dlugotrwalego skupienia. Dlatego nei wyrabiam nawet na dlugich filmach. No i dlatego z dawnego zapedu informatycznego pozostalo tylko hobby na srednim poziomie wtajemniczenia:)

      SM-S908

just d'oh it!

1. ehhh , wukillah 16/11/05 16:40
   mialo byc pod Manersem

   just d'oh it!

   1. [OT] + refleksja , josh 16/11/05 19:28
      tak lekko off-topicowo - czasami ekonomia okazuje się bezlitosna i taniej jest kupic maszyne niz pracowac nad optymalizacją...
      
      Kiedys pensje programistow w porownaniu do ceny sprzetu byly ta male, ze wszystko i wszedzie optymalizowano na potege.
      
      Teraz jest na odwrot - sprzet kosztuje grosze w porownaniu z tym ile trzeba wydac na pensje, wiec coraz czesciej sie nie optymalizuje tylko doklada taniego sprzetu zeby to mielil.
      
      W swojej pracy czasami jeszcze lapie sie na tym, ze chce cos zrobi tak, zeby liczylo/wykonywalo sie szybciej - no i po chwili przychodzi mi na mysl, ze to bez sensu. Strace godzine czy dwie i co to da?
      Jesli juz sie ruszam poprawiania czegos to nie po to, zeby to szybciej dzialalo tylko po to, zeby bylo czytelniejsze, bardziej uniwersalne, zeby dalo sie w przyszlosci gdzies indziej zastosowac. I czesto po takich przerobkach dziala wolniej, ale za to jest bardziej uniwersalne, bardziej czytelne itp...
      
      No, ale w tym watku to ewidentnie trzeba OPTYMALIZOWAĆ i OPTYMALIZOWAĆ. Nie powiem - jest to czesto bardzo ciekawe zajęcie - i choć dzisiaj już często nieopłacalne to jednak są wyjątki...
      1. co kto lubi... , xmac 16/11/05 23:36
         a pozniej taki programista, ktory nie optymalizuje, zarabia srednia krajowa, a ten drugi kilka razy tyle i moze przebierac w ofertach pracy. no chyba, ze to komus wystarcza

         dual&mobile power
         XMAC

         1. no jasne, , josh 20/11/05 14:39
            ...a świstak siedzi i zawija w te swoje sreberka.
            Myślę, że niektórzy mają jakąś manie na punkcie słowa "optymalizacja". Jeden z drugim by tylko siedział i "optymalizował" a fundusze na to brali by chyba z jakiejś fundacji non-profit dla niespełnionych marzeń programistycznych.
            
            Optymalizować to można w nieskończoność, ale tylko w przypadku kilku wąskich dziedzin, jak na przykład funkcje matematyczne do enkodowania i dekodowania strumieni multimedialnych, albo algotyrmy liczące sceny 3D czy podobne rzeczy. Jak będziesz w aplikacji biznesowej optymalizował, żeby transakcja, która wykonuje się raz na jakiś czas trwała 0,2 sekundy zamiast 0,8 sekundy to pierwszy wylecisz za marnowanie czasu.

      2. "zeby bylo czytelniejsze" , wukillah 17/11/05 08:13
         a od tego nie sa przypadkiem komentarze?

         just d'oh it!

         1. jedna z podstawowych zasad dobrego kodu mówi, że , josh 20/11/05 14:35
            "dobrze napisany kod sa w sobie jest najlepszym komentarzem".
            Tak, masz rację: komentarze służą do poprawienia czytelności kodu, ale źle napisanego programu nawet najlepsze na świecie komentarze nie uratują.

         2. Nie , beef 20/11/05 18:18
            To odpowiedź krótka :) A to dłuższa: jeśli potrzebujesz komentarzy w kodzie - Twój styl programowania jest nieczytelny. Poza tym od od braku komentarza gorszy jest nieaktualny komentarz - a jest to wręcz niemożliwe do uniknięcia podczas pracy na "zywym" kodzie. Wystarczy nie bać się długich nazw zmiennych/funkcji, nie pisać "gęstego" kodu, z głową analizować problem i już. Proste ;) Oczywiście rzeczywistość nie jest idealna i czasem tzeba popełnić jakiś komentarz tu i ówdzie, ale to powinien być wyjątek a nie reguła. No i jeszcze jedna rzecz, w której stosować można, a nawet trzeba, komentarze: opisujemy nagłówki funkcji, co dana funkcja robi i co zwraca (np. w formacie Doxygena), dla funkcji udostępnianych na zewnątrz. Liczne komentarze "wewnątrz" kodu to wg szkoły, którą wyznaję, objaw nieumiejętności napisania czytelnego kodu. Ale są oczywiście inne szkoły :)

            this is the time of the revolution
            keepin' it in the right track
            feelin' it in my mind back

Lewy pas to nie kółko różańcowe.

_______________________________

http://jawnesny.pl

1. widzisz, są dwa podejscia , zozol 17/11/05 17:50
   albo samemu siedziec tydzien, robic super optymalizacje po ktorych wszystko przeliczy sie w dwa dni, albo samemu siedziec dwie godziny, odpalic to na szybkiej maszynie (albo kilku) i uzyskać wynik w krótszym czasie i mniejszym nakładem pracy.
   1. marzyciel , BONUS 17/11/05 22:58
      Boski jesteś :)
      
      A tak na poważnie:
      1. znalezienie maszyny (maszyn) może zająć więcej czasu niż tydzień a ilość kasy potrzebnej na ich wynajęcie może być nie mała
      2. przy problemach rozwiązywanych n*n szybko może zabraknąć maszyn które będą wystarczająco silne (a szczegołnie przy tak czołgowych metodach)
      3. ide o zakład że problem jest rozwiązywalny w ciągu poniżej godziny na Twoim sempronie, w ciągu dwóch dni to te 120tys linii przesortuje ręcznie przy pomocy diff, sorta i vi-ja
      
      Pozdro
      BONUS
      1. to o co sie zakladamy? , zozol 17/11/05 23:26
         skrzynka browarów? czy wymiekasz?
         1. jasne , BONUS 18/11/05 08:53
            Canon 350D + kit
            a to i tak po promocji
            
            no to wchodzisz?
            Pozdro
            BONUS
            1. a moze ferrari? , zozol 18/11/05 09:25
               wszystko zrobisz, zeby tylko nie musiec udowadniac swoich słow, prawda? o tyle to moglibysmy sie zakladac, gdyby implementacja tego miala zajac dwa tygodnie, ale wtedy, jak juz pisalem, taniej jest zapuscic kilka kompow na te dwa tygodnie niz tracic czas na kodowanie
               
               przestan sie juz przechwalac jaki jestes wielki magik, pewnie jakbys sam zaimplementowal SETI@Home to by sie calosc na kalkulatorze przeliczyła
               1. Chymmm , BONUS 18/11/05 09:57
                  sorry
                  2 dni pracy po 16 h to jest sześć dniówek (praca w nadgodzinach 200% stawki) - 3000 zł to normalna stawka jaką musiałbyś zapłacić
                  wiedza i myślenie jest cenne, dla skrzynki piwa to nawet nie powinno mi się chcieć w to zajrzeć a tak to szukaj innego frajera co Ci prace na zaliczenie za skrzynke piwa zrobi
                  
                  Pozdro
                  BONUS
                  
                  PS " pewnie jakbys sam zaimplementowal SETI@Home to by sie calosc na kalkulatorze przeliczyła" -udowadniasz kolejne zero pojęcia o temacie - SETI to takie właśnie używanie n kalkulatorów, mamy ileś milionów próbek i dla każdej musimy policzyć FFT i to musi trwać bo dane wejściowe są losowe (SZUM) , w Twoim przypadku tak nie jest dane dają się podzielić na dość niewielki słownik
                  
                  PS2 Nie muszę to być ja sądzę że bwana, czy parę innych osób z TPCB za podobną "nagrodę" byłyby to w stanie zrobić
                  1. no tak , zozol 18/11/05 19:58
                     i jeszcze powiedz ze ta kwota by nie starczyla na wynajecie mocy obliczeniowej do policzenia tego moim sposobem
                     przestan juz sie osmieszac