[alg] documenten vergelijken

[killercow]

Ik ben op zoek naar een techniek/algo waarmee je een bepaald document kunt vergelijken met een grote hoeveelheid andere documenten, uiteraard heb ik zelf nagedacht over verschillende opties, maar ik zou hier graag wat over discussieren.

De bedoeling is dat 100% gelijkende documenten gevonden worden, maar dat ook niet 100% gelijkende documenten gevonden worden.

Ik dacht dat de eerste stap zou zijn dat je een Hash maakt van alle opgeslagen documenten. (loss-less), (dus geen MD5 of RCR, dat heeft alleen nut voor 100% gelijke documenten)

Een nuttige hash had ik als volgt bedacht:
Replace elk woord met een ID (vanuit een (eventueel beperkte tot keywords) lijst met woordjes), en controlleer daarna het aantal overeenkomstige ID's. en sorteer dan op hit-rate.

Of, zoek eerst naar documenten die +- 10% langer of korter zijn, en loop daarna gewoon de string door met een word compare functie.

Misschien werkt een vector search engine ook wel aardig, al denk ik dat je daarbij met vrij grote problemen te maken krijgt omdat je dan een complexe vector (die van het te zoeken document) moet gaan vergelijken met een hele grote andere stapel complexe vectoren. (en dan ben je dus niet veel verder dan de eeste oplossing)

Aangezien die nogal een grijs gebied is, en omdat er vast al eens over na gedacht is door de andere devvers hier, dacht ik laat ik het eens vragen.

[Alarmnummer]

Je kunt allerlei document clusterings technieken toepassen (term vectors zijn een techniek die daarvoor gebruikt worden) om te bepalen of documenten een bepaalde relatie met elkaar hebben.

Maar is dit een algemeen babbel, of heb je meer concrete informatie hoe die documenten van elkaar kunnen verschillen. Heb je een hele zooi documenten, die bv alleen qua layout zijn veranderd.. (dus de inhoud in grote lijnen hetzelfde). Dan is het kwestie om de layout eraf te strippen en eventueel de documenten te normaliseren (stemmen, stopwords eruit slopen).

[edit]
Je moet dus ff beter uitleggen wat je precies wilt want dit is te algemeen

[ Voor 8% gewijzigd door Alarmnummer op 11-05-2005 10:20 ]

[killercow]

Ik heb inderdaad een hele grote (groeiende) stapel teksten, en als er een text bijkomt wil ik de relatie tot eventuele eerdere revisies kunnen vinden.

stemmen/stopwords eruit slopen had ik dus ook bedacht, op die manier hou je dus een lijst met "keywords" over voor ieder document en zo kun je dus vergeleiken.

Ik heb ook een XML parser geschreven waarmee ik de xml structuur kan vinden en deze kan vergelijken, dit helpt om documenten die uit de zelfde software komen te vinden, en zo dus al een selectie te kunnen maken.

het gaat in principe alleen om xml doc's, dus

Het makkelijkste zou natuurlijk gewoon vragen om document nummers bij de invoer, of om unieke key's, maar het proces is grotendeels geautomatiseerd en vindt zelf de docs. (soort van webspider, die dus ook pages moet kunnen matchen als ze op andere url's te vinden zijn, bijvoorbeeld mirrors van documenten.)

[Alarmnummer]

Maar wil je willekeurige documenten met elkaar kunnen matchen, of kan je de selectie beperken. Bv: ze staan in dezelfde dir, maar hebben alleen een ander versie nummer. Als je echt 0.0 informatie krijgt en dus alles met elkaar moet checken, tja... dan gaat het denk ik wel lastig worden om te bepalen of documenten een relatie met elkaar hebben. Als je xml documenten bepaalde namespaces hebben zou je daar al een beetje mee kunnen stoeien. Als ze dezelfde namespace hebben, dan mogen ze met elkaar vergeleken worden, anders neit. Hiermee kan je de hoeveelheid te vergelijken documenten drastisch reduceren.

Een ander voordeel is dat je XML gigantisch goed gestructureerd is (veel beter dan een standaard html pagina). Daarom vermoed ik dat er ook betere methodes zijn voor XML document vergelijkingen dan standaard document vergelijkingen.

[ Voor 17% gewijzigd door Alarmnummer op 11-05-2005 10:46 ]

[pjvandesande]

Moeten de bestanden identiek zijn of moeten ze op elkaar lijken. Want als je over mirrors praat moeten het identieke bestanden zijn lijkt mij. En die zijn natuurlijk niet moeilijk te vergelijken.

Je hoeft dat alleen de stream's te vergelijken.

[killercow]

Het gaat om een systeem dat directe 100% zuivere mirros kan vinden (dat kan wel via CRC of MD5 oid), maar het gaat vooral om documenten die soort van op elkaar lijken.

Ik wil bijvoorbeeld 2 documenten kunnen vinden die 95% op elkaar lijken, mischien is er wel een hash techniek die een getal terug geeft, en dan van een soortgeleik document een getal terug geeft dat maximaal 5% van dat andere getal afwijkt. Als je een CRC hash neemt dan heb je bij documenten die 99.9% op elkaar lijken al een heel andere hash, dus daar heb je niets aan. Ik heb juist een verkorte hash nodig van de brontext die dus erg veel op de andere hash lijkt.

Dan kan ik eventueel de hash vergelijken via levenstein oid.

Of ik wel of niet de dataset kan verkleinen is niet echt van belang natuurlijk, dat is puur optimalisatie van de omgeving. (niet dat het niet veel scheelt hoor, maar toch)

[mr.inno]

je zou het op de zelfde manier kunnen doen als bij wikipedia..
maar dat kijkt per regel. dus in hoeverre dat is wat je zoekt weet ik niet.

[djluc]

Is dit niet een beetje wat Diff doet op unix systemen?

[killercow]

djluc schreef op woensdag 11 mei 2005 @ 12:12:
Is dit niet een beetje wat Diff doet op unix systemen?

gedeeltelijk, maar diff kan het niet HEEEEEL snel (en mischien iets minder accuraat)

[Robbemans]

http://www.scootersoftware.com/

Biedt Beyond Compare aan met complete scripting mogelijkeheden.

[Alarmnummer]

Robbemans schreef op dinsdag 17 mei 2005 @ 14:23:
http://www.scootersoftware.com/

Biedt Beyond Compare aan met complete scripting mogelijkeheden.

Lees aub zijn topic ff beter door voordat je reageert. Hij zoekt de techniek, niet een product.

[killercow]

Robbemans schreef op dinsdag 17 mei 2005 @ 14:23:
http://www.scootersoftware.com/

Biedt Beyond Compare aan met complete scripting mogelijkeheden.

Dat product is gewoon bedoelt om verschillen in documenten te vinden, dat is een stukje code van een paar honder regels (max), dat zoek ik dus niet.

Ik had wel wat dingen op wikipedia gevonden zoals "robust audio hashing" maar tjah, dat is wel erg op audio toegespitst.

[Soultaker]

De snelste methode om te zoeken is als je voor elk document een soort 'fingerprint' kunt genereren waar je makkelijk mee kunt vergelijken. Dat hoef je namelijk maar een keer per document te doen en je hoeft dan niet alle documenten met alle anderen te vergelijken om matches te vinden. Als het om natuurlijke taal gaat, is het zinnig om een document te reduceren tot een lange lijst van woorden (je identificeert dan eerst alle woorden en gooit alle interpunctie en lay-out weg).

Wat Alarmnummer ook al noemde is het berekenen van een document vector per document; daarin staat dus voor elk woord de relatieve frequentie waarmee het voor komt. Daarvoor is het praktisch om een vast, globaal woordenboek te hebben. Documenten kun je dan snel vergelijken omdat je de document vectors kunt vergelijken in de Euclidische ruimte.

Nadeel van deze methode is dat je zo geen documenten vind die een paragraaf of een hoofdstuk gemeen hebben maar verder verschillen.

Een iets simpelere methode is een vaste hashcode die je baseert op het voorkomen van bepaalde woorden in de tekst. Je neemt dan bijvoorbeeld een 2048-bits waarde als fingerprint met alle bits op 0. Voor elk woord dat voorkomt in het document bereken je met een hashfunctie een code in het bereik 0..2048 en zet de corresponderende bit op 1. Documenten met dezelfde fingerprint hebben nu grote kans om dezelfde woorden te bevatten. Near-matches kun je vinden met een soort Manhatten distance tussen twee fingerprints (het aantal bits dat niet overeenkomt).

Nadeel van deze methode is dat hele verschillende woorden op dezelfde bit afgebeeld worden en dat frequenties niet meegenomen worden. Voordeel is wel dat je makkelijker documenten kunt samenvoegen en delen van documenten kunt vinden.

[T-MOB]

killercow schreef op woensdag 11 mei 2005 @ 11:43:
Ik wil bijvoorbeeld 2 documenten kunnen vinden die 95% op elkaar lijken, mischien is er wel een hash techniek die een getal terug geeft, en dan van een soortgeleik document een getal terug geeft dat maximaal 5% van dat andere getal afwijkt. Als je een CRC hash neemt dan heb je bij documenten die 99.9% op elkaar lijken al een heel andere hash, dus daar heb je niets aan. Ik heb juist een verkorte hash nodig van de brontext die dus erg veel op de andere hash lijkt.

Zo'n hash zou een redelijk waardeloze hash zijn voor de gangbare gevallen waarin hashes gebruikt worden. Als er een duidelijke relatie is tussen de inhoud en de hash is ie namelijk zo gekraakt

Daarnaast is het wat jij wil nogal onmogelijk. Als je namelijk een textbestand hebt van 1kb dan heb je 8^1024[ mogelijk binaire combinaties. Met een 128bits hashingsalgoritme kun je maar 2¹²⁸ verschillende combinaties aanduiden. De verhouding tussen combinaties in de hash en combinaties in de brontext is dus 1: 2²⁹⁴⁴ (2³⁰⁷² / 2¹²⁸). Kort door de bocht moeten er dus minimaal 368 bytes veranderen wil je dit kunnen teruglezen in een 128bits representatie van de text.

Een echt snelle methode om documenten te vergelijken bestaat volgens mij niet. Maar aangezien het om XML docs gaat zou je kunnen proberen om het gebruik van een duur vergelijkingsalgoritme te minimaliseren. Je kijkt eerst of de structuur overeenkomt, zo ja dan match je op een aantal essentiële punten in het document. In HTML zouden dat de Hx'en oid zijn. Als daar voldoende overeenkomst in zit match je op vaker voorkomende elementen. Pas als die match voldoende overeenkomst biedt ga je naar een duur vergeijkingsalgoritme. Een kwestie van documenten met verschillen zo efficient mogelijk uitsluiten dus..

Om tot zo'n vergelijkingsalgoritme te komen zou je er volgens mij best goed aan doen om in de source van diff te kijken hoe dat geïmplemteerd is. Een diff-achtige implementatie in PHP ( (source)* is in elk geval een stuk minder snel. Voor lange strings zelfs compleet onbruikbaar...

* credits voor het script voor madwizard & Jurgle

[killercow]

T-MOB,

Het hoeft ook niet een fool-proof hash te zijn, meer een soort van quick lookup.
als er daarna een 10 tal collisions/matches over blijven is dat niet zo'n punt, dan kan ik daar dus wel een duurder algoritme over heen gooien (zoals levenstein), die controlleerd of de documente echt wel op elkaar lijken.

Ik heb ondertussen bezig met de dictionary achtige manier aan het testen, via een rij met woorden kan ik zo een lange rij van id's opzoeken per genormaliseerde en gestemde text. Dit is in ieder geval al een stapje dichter bij. maar een snelle hash zou natuurlijk veel beter zijn.

Aangezien de meeste hash functies juist geschreven zijn om niet te valideren bij kleine changes (bit errors etc) is het moeilijk om een functie te vinden die juist wel geleikende hashes genereert bij lichte afwijking.

[staefke]

n-m gram match misschien iets voor je ? eventueel kun je kijken naar de code van lucene, een open-source full text search engine die ook 'fuzzy' searches ondersteunt (je mag typefouten maken ).

[ Voor 15% gewijzigd door staefke op 17-05-2005 16:46 ]

[joepP]

Een hashfunctie hiervoor ontwikkelen lijkt me erg lastig. Dat betekent concreet dat je je complete bibliotheek aan documenten op een eendimensionale lijn gaat afbeelden (hashen), en dan ook nog verwacht dat ongeveer gelijke documenten op dezelfde locatie uitkomen.

Ik vrees dat je toch richting een soort van dictionary-achtige-woordteller zal moeten gaan.

[Soultaker]

Los van de suggesties die ik al eerder deed, moet je je eerst afvragen hoe je gelijkenis definieert (of wat je ongeveer een acceptabele definitie vind).

[ Voor 21% gewijzigd door Soultaker op 17-05-2005 17:43 ]

[Gomez12]

Als je nou gewoon top-down gaat hashen. Eerst het hele document, komt dit overeen dan per namespace, komt dit niet overeen dan per regel, komt dit niet overeen dan levenstein.

Dan zijn 2 identieke documenten zo gevonden, documenten met 1 namespace met verschillen zijn ook vrij snel, je kan zelfs nog gaan diffen in de namespaces die verschillen. Maar het hangt er allemaal vanaf wat jij als 2 verschillende documenten ziet. Want verschillen kunnen ook zitten in het aanbrengen van een punt etc.

[killercow]

Gomez12 schreef op dinsdag 17 mei 2005 @ 18:08:
Als je nou gewoon top-down gaat hashen. Eerst het hele document, komt dit overeen dan per namespace, komt dit niet overeen dan per regel, komt dit niet overeen dan levenstein.

Dan zijn 2 identieke documenten zo gevonden, documenten met 1 namespace met verschillen zijn ook vrij snel, je kan zelfs nog gaan diffen in de namespaces die verschillen. Maar het hangt er allemaal vanaf wat jij als 2 verschillende documenten ziet. Want verschillen kunnen ook zitten in het aanbrengen van een punt etc.

Dit lijkt mij naast de dictionary versie wel een vrij goede oplossing, het duurt wel behoorlijk lang bij een grote hoeveelheid documenten, maar ik denk dat het een stap in de goede richting is.

Als ik per 512 bytes een korte hash maak, moet ik dus een samengestelde hash kunnen bouwen.

[hash1][hash2][hash3][hash4][hash5], deze sla ik dan per document op, en dan kan ik de hash die ik nieuw vindt, via een aangepaste levenstein wel vergeleiken. nadeel is dat kleine shifts aan het begin alles overhoop gooien, en dus de match verklooien.

Naja, ik ga nog wel even door met m'n dictionary en vector systeem (al moet voor het fector systeem ongeveer alle document vectors in memmory gaan houden, wat ook niet echt tof is)

[Verwijderd]

Hallo iedereen,

Ik ga de komende paar weken in het kader van mijn afstudeeropdracht bezig zijn met het matchen van gegevens. Ik zocht eens op google en kwam zo op dit topic uit.

De meeste resultaten die ik kreeg op het matchen gaan ervan uit dat je 1 begrip wilt matchen met een stuk tekst. Dit is echter niet wat ik wil, de aanleiding van dit topic komt meer in de buurt, dus ik dacht, ik reageer hier om te kijken of er meer ideeen zijn.

Ik wil niet zozeer stukken tekst met elkaar matchen, maar zit meer met het volgende scenario:

Er zijn een aantal array's met begrippen, zo is er bijvoorbeeld een array met alle landen van de wereld. Nu wil ik stukken text matchen tegen deze array's om zo relaties zichtbaar te maken.
Voorlopig zit in de bedoeling dat ik ieder woord in de tekst afloop en match tegen ieder woord in de arrays, dit is echter een langdurig proces. Ik heb al een aantal methoden bedacht om dit te verkorten, bijvoorbeeld door een dictionary aan te maken met 26 ingangen (A-Z) met daarachter de begrippen en ieder woord voordat ik deze ga matchen te sorteren op beginletter.

Ik vroeg mij af of hier mensen zijn die enkele ideeen hebben over het matchen van begrippen in arrays tegen stukken tekst. En of hier algoritmes voor zijn om dit te vergemakkelijken.

Ook ideen over het volgende zijn welkom:
Er is bijvoorbeeld ook een array met namen van personen. Wanneer namen van personen en namen van landen overeen komen en/of uit meerdere woorden bestaan, hoe kan ik deze het beste matchen.

Dit geldt uiteraard ook voor landen die uit meerdere woorden bestaan, zal ik ieder woord uit de tekst matchen met ieder woordt in de array afzonderlijk? bij 'rio de janero' komt het woordje 'de' uit als match, dit is uiteraard niet gewenst.

Alle suggesties zijn welkom.

[H!GHGuY]

Verwijderd schreef op dinsdag 24 mei 2005 @ 16:26: lange tekst

er bestaan verschillende tekstsearch algoritmen, maar wat jij zoekt is volgens mij een van volgende:
suffixbomen of suffixarrays.

aangezien je veel woorden in een tijdelijk niet veranderende tekst zoekt.

je construeert je suffix-array/boom en dan kun je door heel simpel binary search of afdalen in je boom
alle plaatsen in je tekst vinden waar je woord voorkomt.

je algo is dan dus O(n) (als'k me niet vergis) voor de opbouw van je datastructuur en dan is elke opzoeking O(m).
(n = lengte van je tekst, m = lengte van het woord dat je zoekt)

[alienfruit]

Zou ik even op mogen inhaken zijn er ook bepaalde algoritmes of technieken voor het vergelijken van grafische documenten met elkaar? Meer het detecteren van de verschillen van een bepaald bestand (ik wil twee versies vergelijken.)

[Gomez12]

Verwijderd schreef op dinsdag 24 mei 2005 @ 16:26:
Hallo iedereen,

Ik ga de komende paar weken in het kader van mijn afstudeeropdracht bezig zijn met het matchen van gegevens. Ik zocht eens op google en kwam zo op dit topic uit.

De meeste resultaten die ik kreeg op het matchen gaan ervan uit dat je 1 begrip wilt matchen met een stuk tekst. Dit is echter niet wat ik wil, de aanleiding van dit topic komt meer in de buurt, dus ik dacht, ik reageer hier om te kijken of er meer ideeen zijn.

Ik wil niet zozeer stukken tekst met elkaar matchen, maar zit meer met het volgende scenario:

Er zijn een aantal array's met begrippen, zo is er bijvoorbeeld een array met alle landen van de wereld. Nu wil ik stukken text matchen tegen deze array's om zo relaties zichtbaar te maken.
Voorlopig zit in de bedoeling dat ik ieder woord in de tekst afloop en match tegen ieder woord in de arrays, dit is echter een langdurig proces. Ik heb al een aantal methoden bedacht om dit te verkorten, bijvoorbeeld door een dictionary aan te maken met 26 ingangen (A-Z) met daarachter de begrippen en ieder woord voordat ik deze ga matchen te sorteren op beginletter.

Ik vroeg mij af of hier mensen zijn die enkele ideeen hebben over het matchen van begrippen in arrays tegen stukken tekst. En of hier algoritmes voor zijn om dit te vergemakkelijken.

Ook ideen over het volgende zijn welkom:
Er is bijvoorbeeld ook een array met namen van personen. Wanneer namen van personen en namen van landen overeen komen en/of uit meerdere woorden bestaan, hoe kan ik deze het beste matchen.

Dit geldt uiteraard ook voor landen die uit meerdere woorden bestaan, zal ik ieder woord uit de tekst matchen met ieder woordt in de array afzonderlijk? bij 'rio de janero' komt het woordje 'de' uit als match, dit is uiteraard niet gewenst.

Alle suggesties zijn welkom.

Ideetje, laat hem alle matches loggen, en vergelijk dan na een tijdje het eerst gevonden woord met alle matches, dan verklein je je zoek-arrays een stuk dus ,in een stuk tekst waar : door een deur lopen voorkomt als tekst kan je alle engelse woorden schrappen. Hiermee krijg je gelijk je relaties na een x aantal documenten, want dan zie je vanzelf dat woord x altijd gelijk na woord y voorkomt.

En zowiezo niet alle woorden gaan matchen, maar alle woorden die bijv groter zijn dan 6 letters pas gaan matchen.
En kijk eerst naar de belangrijkheid van een tekst ( in html is h1 belangrijker dan h6 etc. )
En kijk eens naar freeware searchtools hoe deze het doen.

[H!GHGuY]

alienfruit schreef op dinsdag 24 mei 2005 @ 18:24:
Zou ik even op mogen inhaken zijn er ook bepaalde algoritmes of technieken voor het vergelijken van grafische documenten met elkaar? Meer het detecteren van de verschillen van een bepaald bestand (ik wil twee versies vergelijken.)

er bestaan alleszins methodes om snel (adhv een schets bvb) foto's/tekeningen etc te zoeken...

wat er dan gebeurt (als 'k het me nog een beetje herinner) is iets adhv wavelets dacht'k:
de C en D coefficienten van de wavelet-transformatie worden bijgehouden.
dan wordt een drempelwaarde gekozen waarbij alle absoluate waarden van C/D groter zijn dan deze waarde behouden wordt.
vervolgens worden de resterende waarden gereduceerd tot +1,0,-1

dit proces doe je ook met het te vergelijken beeld, en zo bekom je 2 2D tabellen met +1,0,-1 waarden die je kan vergelijken (met toestaan van beperkt aantal fouten!!)

als je enkel de verschillen wilt:
je past op beide de wavelet transformatie toe en dan kun je die C/D coefficienten vergelijken met een max-verschil die je instelt of zo

[ Voor 10% gewijzigd door H!GHGuY op 24-05-2005 23:04 ]

[MSalters]

Hash functies werken slecht, omdat dat een een-dimensionaal resultaat oplevert. Afstandsmaten in die een-dimensionale ruimte zijn bovendien voor een "echte" hash random, en dus is het onbruikbaar.

De correcte methode voor deze categorie problemen is om zo'n document naar een geschikte hoog-dimensionale ruimte te mappen. Hoe hoog-dimensionaal hangt af van het aantal documenten wat je hebt, maar ik vermoed dat O(logN) een behoorlijk goede benadering is. Voor 1000 documenten zou je dus ongeveer 10 onafhankelijke indices moeten gebruiken. Vervolgens kun je dan een (Euclidische of block) afstandsmaat gebruiken.

Een belangrijke dimensie voor de TS lijkt me het XSD of DTD: als die verschillen dan verschillen de documenten waarschijnlijk ook. Verder kun je nog kijken naar fragmenten: op basis van je algemene woordfrequenties, welke fragmenten zijn dan bijzonder? Neem de 10 meest onwaarschijnlijke fragmenten van circa 4 woorden uit elk document, en vergelijk die (resultaat: 0-10 gelijke fragmenten)

[Verwijderd]

Bedankt voor de reacties op mijn stukje, ik zal zeker eens verder kijken in de genoemde richtingen. Uiteraard blijf ik openstaan voor eventueel aanvullende reacties.

[killercow]

Verwijderd schreef op woensdag 25 mei 2005 @ 09:58:
Bedankt voor de reacties op mijn stukje, ik zal zeker eens verder kijken in de genoemde richtingen. Uiteraard blijf ik openstaan voor eventueel aanvullende reacties.

(had je ook door dat mijn laatste post 6 dagen voor jouw post was?) ik dacht niet dat mijn topic al dood was. dat er wat dagen overheen gaan voordat ik prototypes getest heb, en voordat mensen weer zinnige reacties kunnen geven lijkt me niet meer dan logisch bij een thread als deze.

Misschien verstandig om een eigen topic te openen? (of is de tag [alg] tegenwoordig synoniem met [verzamlen/discussie]?

Anyway, misschien hebben onze vragen wel raakvlakken en kunnen we er samen eens naar kijken, maar vooralsnog denk ik dat je toch wel een behoorlijk andere vraag stelt dan ik, en dus beter een los topic kan openen. (geld ook voor alienfruit denk ik)

Of we moeten hier idd een topic over maken met betrekkening tot zoeken tussen objecten met behulp van multidimensionale vergeleikings technieken.

[Robbemans]

Nogmaals:

http://www.scootersoftware.com/

Biedt Beyond Compare aan met complete scripting mogelijkeheden.

En nu niet meteen beginnen over 'lees zijn topic nou es goed voordat...'

BC biedt een snelle manier om, aangestuurd via scripts, documenten te vergelijken en een positief of negatief gesultaat terug te geven voor een match of niet. Het lijkt op UNIX diff, maar die is erg langzaam.

Wellicht dat je met deze tool toch kan wat je wil.

[killercow]

@Robbermans
Het gaat hier niet om een x aantal bestandjes die met elkaar vergeleken moeten worden.
Maar om bijvoorbeeld 100.000 bestanden. waarbij we een nieuw bestand loosly willen matchen.

Dit kan natuurlijk voor geen meter met string compare actiche technieken doen, tenzij alles in Memmory hebt staat en je een 8 way dual core opteron hebt om de search te doen.

ps, ik ken beyond compare, en hoe mooi het ook mag zijn, het is niet bruikbaar omdat de zoek techniek niet bedoeld is voor dit soort dingen.
Het gaat hier juist om het zoeken naar die juiste techniek. niet het daarom heen gebouwde product (dat bouw ik toch wel zelf)

[tdn135]

Total Commander --> Directories vergelijken Misschien...

[ Voor 19% gewijzigd door tdn135 op 25-05-2005 12:35 ]

[killercow]

nljagfan schreef op woensdag 25 mei 2005 @ 12:35:
Total Commander --> Directories vergelijken Misschien...

Read the F**king Thread!, wie zegt dat die bestanden uberhaupt in dir's staan? en zo ja, dan zou dat gewoon een van de kernmerken zijn, niets meer, niets minder.

[Verwijderd]

Damn killercow, ik vind je reacties steeds meer weg krijgen van flaming. De mensen proberen gewoon een oplossing voor je probleem te vinden en ideeen te uitten, als je er niets aan hebt ok, dan hoef je nog niet te schelden.

Trouwens, het was niet mijn bedoeling om met mijn opmerking je thread te 'stelen'. Ik zag alleen dat de thread al een paar dagen niet actief was en omdat mijn vraag meer een zijspoortje is op jou onderzoek dacht ik dat het handig was om het hier bij te posten, wellicht dat je aan de reacties die erop worden gegeven ook iets hebt.

Voor mijn vraag is het niet erg nuttig om een hele nieuwe thread te starten denk ik, omdat ik niet wacht op 3 paginas reacties op mijn vraagstelling, ik wilde gewoon naar wat ideeen informeren.

In ieder geval hoop ik dat je verder nog succes boekt, want wat je wilt doen lijkt me erg lastig. Zeker nog wel lastiger dan mijn vraagstuk.

[killercow]

Verwijderd schreef op woensdag 25 mei 2005 @ 16:06:
snap..

Ik snap gewoon niet dat mensen zoals hierboven dingen als beyond compare aangeven als een oplossing. Ik heb bij dat soort progjes atijd meteen een gevoel dat mensen niet lezen maar meteen gaan roepen dat ik X of Y moet gebruiken. (beetje het zelfde als dat je zou vragen wat een betere text editor is ultraedit/textpad, dan gaan mensen ook meteen roepen) (volgens mij zien ze de topic titel in de active-topics, en lezen ze bijna 0)

Dat jij de thread niet wilt "stelen" snap ik ook wel, maar ik denk dat het geen optimaal resultaat geeft als we allemaal verschillende vragen gaan stellen in een topic. Als we echter over het onderliggende zoeken/indexeren gaan discussieren dan lijkt het me juist perfect om met meer lotgenoten in een thread te vragen/redeneren.

Geen bad feelings naar jouw dus!, maar laten we de thread ontopic houden.

[Robbemans]

@Killercow

Lezen is idd soms moeilijk, maar houdt er rekening mee dat als je een vraag stelt en mensen de MOEITE nemen om te reageren dit feitelijk een gratis reactie is. Als je dit als ruis opvat, kun je de opmerkingen compleet negeren om niet te verzanden in wat wel en niet nuttig is. Persoonlijk denk ik dat BC je kan helpen als 'duurder algorithme', maar ik begrijp dat je eerste schifting het belangrijkst is...

Wat ik zou doen is alle woorden tellen in een document en deze lijst vergelijken met de lijst van een ander document. Hiermee kun je redelijk snel een eerste schifting doen. Eventueel kun je dit fuzzy doen, maar ik zou een soundex algotrithme gebruiken om woorden te sparen. Ook onbelangrijke woorden kun je filteren (zoals je al aangegeven hebt). Hope this helps.

[killercow]

Robbemans, Ok ok,

De laatste alinea, daar hebben we wel wat aan denk ik.

Ik heb ondertussen de dictionary wat verbeterd, woorden die niet vaak voorkomen (procentueel over het geheel) krijgen automatisch een hogere rate als ze matchen.

(dus als er maar 2 document zijn met een bepaald type nummer of merknaampje linken deze vrij goed op elkaar.)
Nu met ik nog even testen hoeveel en welke woorden ik ga gebruiken om te matchen. Woorden die in meer dan *% van de documenten voorkomen zijn niet relevant (noise words) en kunnen dus automatisch gefilterd worden.

Door daarnaast bij te houden hoe vaak woorden bij elkaar gevonden worden, (en wat de afstand in chars tussen die 2 woorden is kan ik met een vrij simpel a* pathfinding scriptje uitvinden wat de afstand tussen 2 woorden is) hoe relevant zijn 2 keywords tegen over elkaar (ook als ze nog nooit samen in een document gestaan hebben) deze index generate ik nu snachts, maar mij E450's hebben het er zwaar mee (uurtje of 8 crunshen per index).

Ook zoeken naar uigebreidere matches gaan vrij goed via die index, als ik woord x en Y gevonden heb, kan ik kijken of Z (die dicht bij x en y licht) ook in de docs zit, en hoef ik niet alle keywords te bekijken.

We're getting there!

[Verwijderd]

Misschien ook een idee:

Een array maken van alle unieke woorden uit een tekst en hoe vaak deze voorkomen. Dan deze twee arrays element voor element met elkaar vergelijken en een eventuele afwijking toestaan. Een grotere afwijking toestaan op veel voorkomende woorden en een kleinere op weinig voorkomende woorden... hier is uiteraard een algoritme voor te bedenken.

[H!GHGuY]

Verwijderd schreef op vrijdag 27 mei 2005 @ 14:43:
Misschien ook een idee:

Een array maken van alle unieke woorden uit een tekst en hoe vaak deze voorkomen. Dan deze twee arrays element voor element met elkaar vergelijken en een eventuele afwijking toestaan. Een grotere afwijking toestaan op veel voorkomende woorden en een kleinere op weinig voorkomende woorden... hier is uiteraard een algoritme voor te bedenken.

hoe zou je dat doen zonder ofwel een O(n²) algo ofwel door eerst ALLE woorden in je tekst op te slaan?

[kvdveer]

Ik heb helaas niet de tijd gehad om het laaste deel van deze draad te lezen dus misschien is mijn idee al genoemd, sorry daar voor dan.

Je noemde dat Levenstein te traag was, daar ga ik ook vanuit. Levenstein gaat echter uit van letters, als je levenstein implementeerd met in plaats van letters woorden (al dan niet gestemd) moet je toch al een flink end komen. Waarschijnlijk wordt het alsnog O(N²), maar omdat je vroeg kunt falen: nadat je levensteinmutaties boven een bepaalde drempel komen is je vergelijking gefaald. Als je die drempel laag genoeg legt, moet het O(n²) geen probleem zijn. Een hash gaat je echt niet lukken namelijk... Om performance te winnen zou je zo'n constructie kunnen verzinnen:

code:

constant DREMPEL = 50; // zelf optimaliseren... :)

method vergelijk(doc1, doc2) :: int
    if(abs(doc1.wordcount - doc2.wordcount) > DREMPEL) return 0;
    result = word_levenstein(doc1,doc2, DREMPEL);
    if(result == -1 ) return 0
    return 100-result;

Met die eerste vergelijking zal de meerderheid van je documenten vroeg falen, en zal je rekentijd meevallen. Door levenstein zo te implementeren dat 'ie het opgeeft nadat je een bepaalde drempel hebt gehaald, kun je nog meer vroeg falen.
Alleen de documenten die op elkaar lijken zullen veel rekenwerk vereisen.

Eventueel kun je nog verder klusteren: als doc1 very simular to doc2 and comparedoc not simular to doc1 ==> comparedoc not simular to doc2;
Je zult dan een soort van "simular to" en "very simular to" moeten implementeren. Ook dat kan weer vergelijkingen schelen, vooral omdat je de eerste relaties kunt berekenen bij het opslaan van doc1 en doc2.

[Soultaker]

Die maat heet Levenshtein afstand (met een h dus) en als je een drempel gebruikt dan kan 'ie in O(d*(N+M)) (waarbij d dus de maximale edit distance is die je wil berekenen). Dit werkt trouwens voor elke edit distance die je wil gebruiken.

[ Voor 4% gewijzigd door Soultaker op 28-05-2005 21:34 ]

[Verwijderd]

Misschien is dit interessant
http://cartography.geog.uu.nl/students/dejongh/2.htm