Archief - Closest match array

Het archief is een bevroren moment uit een vorige versie van dit forum, met andere regels en andere bazen. Deze posts weerspiegelen op geen enkele manier onze huidige ideeën, waarden of wereldbeelden en zijn op sommige plaatsen gecensureerd wegens ontoelaatbaar. Veel zijn in een andere tijdsgeest gemaakt, al dan niet ironisch - zoals in het ironische subforum Off-Topic - en zouden op dit moment niet meer gepost (mogen) worden. Toch bieden we dit archief nog graag aan als informatiedatabank en naslagwerk. Lees er hier meer over of start een gesprek met anderen.
S

Sick-Boy

Legacy Member
Ik zoek een snelle manier om de closest match tussen 2 arrays te vinden.
De bedoeling is om een dynamische array te vergelijken met een statische array en de beste combinatie van elementen te vinden.

Lijst 1: A, B, C, D
Lijst 2: X, Y, Z

Dan is A/Z, B/Y, C/X de beste combinatie als score(A,Z) + score(B,Y) + score(C,X) > score(B,Z) + score(C,Y) + score(D,X), ...

Ik was met permutaties begonnen en dan score van de elementen op dezelfde plaats in de arrays aan het berekenen, maar aangezien dat N! complex is, duurt de berekening nogal lang voor meer dan 10 elementen (en ik hou rekening met overbodige berekeningen).

Dus als iemand mij kan helpen, leave a comment below :).
C

Cycloon

Legacy Member
Mocht het maar O(n!) zijn dan moet je dringend een paper schrijven over je ontdekking. Dit is eerder O(n^n). Maar wat je wil bereiken kan je gewoon niet sneller doen. Het enige wat je kan doen is zo goed mogelijk optimaliseren om bepaalde combinaties geen 2 keer te berekenen.
S

Sick-Boy

Legacy Member
Cycloon zei:
Mocht het maar O(n!) zijn dan moet je dringend een paper schrijven over je ontdekking. Dit is eerder O(n^n). Maar wat je wil bereiken kan je gewoon niet sneller doen. Het enige wat je kan doen is zo goed mogelijk optimaliseren om bepaalde combinaties geen 2 keer te berekenen.
Klik om te vergroten...

Right, N! permutaties, de berekening ervan kan wel exponentieel zijn veronderstel ik.

De combinaties die worden berekend worden opgeslagen om redundantie te vermijden.
C

Cycloon

Legacy Member
Sick-Boy zei:
Right, N! permutaties, de berekening ervan kan wel exponentieel zijn veronderstel ik.

De combinaties die worden berekend worden opgeslagen om redundantie te vermijden.
Klik om te vergroten...

De combinaties opslaan zorgt wel voor extra overhead, want je moet immers telkens gaan zoeken in je structuur.

De beste tactiek die je kan toepassen is Alpha-beta pruning - Wikipedia, the free encyclopedia naar mijn mening. Je gaat alle oplossingen af, maar van zodra een deeloplossing al slechter is dan je huidige beste oplossing daal je de zoekboom niet meer verder af. Alles wat zich onder die node bevindt zijn dan toch slechtere oplossingen. Jammer genoeg geeft dit geen goed effect wanneer alle scores heel dicht bij elkaar liggen.
N

NeverwinterX

Legacy Member
Het is wel degelijk O(N!). Je berekent een matrix A met A[j] score(list1, list2[j]) en daarvan zoek je de n-rooks met de maximale som. Dat betekent dus alle n-rooks (en hun som) zoeken en dus alle permutaties van 1...N = N!.

nevermind, wat hier stond klopt niet.

Is het trouwens echt noodzakelijk om de beste oplossing te hebben of volstaat een benadering? Anders kan je een greedy aanpak of andere heuristiek gebruiken.
S

Sick-Boy

Legacy Member
Cycloon zei:
De combinaties opslaan zorgt wel voor extra overhead, want je moet immers telkens gaan zoeken in je structuur.
Klik om te vergroten...

Het is Prolog code, door gebruik te maken van tabling is die overhead zeer beperkt (berekenen duurt langer ^^).

De beste tactiek die je kan toepassen is Alpha-beta pruning - Wikipedia, the free encyclopedia naar mijn mening. Je gaat alle oplossingen af, maar van zodra een deeloplossing al slechter is dan je huidige beste oplossing daal je de zoekboom niet meer verder af. Alles wat zich onder die node bevindt zijn dan toch slechtere oplossingen. Jammer genoeg geeft dit geen goed effect wanneer alle scores heel dicht bij elkaar liggen.
Klik om te vergroten...

Het is de generatie van de permutaties die tijd nodig heeft, of het testen van alle waardes. Ik weet niet of een early-stopping veel verandert aan de tijds-consumptie.

NeverwinterX zei:
Het is wel degelijk O(N!). Je berekent een matrix A met A[j] score(list1, list2[j]) en daarvan zoek je de n-rooks met de maximale som. Dat betekent dus alle n-rooks (en hun som) zoeken en dus alle permutaties van 1...N = N!.
Klik om te vergroten...


Volgens Wikipedia is het berekenen van de permutaties O(N log N). Maar dat is eigenlijk maar bijzaak :p.


nevermind, wat hier stond klopt niet.

Is het trouwens echt noodzakelijk om de beste oplossing te hebben of volstaat een benadering? Anders kan je een greedy aanpak of andere heuristiek gebruiken.
Klik om te vergroten...

Het is een classificatie probleem waarbij een tekst (lijst van woorden) wordt vergeleken met een representatieve lijst van woorden uit een bepaalde klasse. Dus voor elke klasse moet zo'n berekening gebeuren.
Het is toch wel de bedoeling om de beste oplossing te hebben.
C

Cycloon

Legacy Member
NeverwinterX zei:
Het is wel degelijk O(N!). Je berekent een matrix A met A[j] score(list1, list2[j]) en daarvan zoek je de n-rooks met de maximale som. Dat betekent dus alle n-rooks (en hun som) zoeken en dus alle permutaties van 1...N = N!.
Klik om te vergroten...


Edit: Toch maar eens verder over nagedacht. O(n^n) is inderdaad een overschatting. De volgorde waarin je dynamische array staat maakt eigenlijk niet uit voor je berekening, waardoor je enkel éénmalig de nodige permutaties moet berekenen met de 2de array. Ik zat ook nog te denken over het feit dat je voor elke permutatie binnen de dynamische array ook opnieuw moest berekenen. Je zou daarom de dynamische array kunnen sorteren en kunnen optimaliseren bij lange series van dezelfde tekens.
N

NeverwinterX

Legacy Member
Cycloon zei:
Edit: Toch maar eens verder over nagedacht. O(n^n) is inderdaad een overschatting. De volgorde waarin je dynamische array staat maakt eigenlijk niet uit voor je berekening, waardoor je enkel éénmalig de nodige permutaties moet berekenen met de 2de array. Ik zat ook nog te denken over het feit dat je voor elke permutatie binnen de dynamische array ook opnieuw moest berekenen. Je zou daarom de dynamische array kunnen sorteren en kunnen optimaliseren bij lange series van dezelfde tekens.
Klik om te vergroten...

Mja de matrix is symmetrisch, daar had ik nog niet aan gedacht, dus dat kan je verder uitbuiten. En als er in de dynamische veel dezelfde elementen voorkomen, is het natuurlijk ook wat gemakkelijker dan allemaal aparte.

Sick-Boy zei:
Volgens Wikipedia is het berekenen van de permutaties O(N log N). Maar dat is eigenlijk maar bijzaak :p.
Klik om te vergroten...

Link?


Sick-Boy zei:
Het is een classificatie probleem waarbij een tekst (lijst van woorden) wordt vergeleken met een representatieve lijst van woorden uit een bepaalde klasse. Dus voor elke klasse moet zo'n berekening gebeuren.
Het is toch wel de bedoeling om de beste oplossing te hebben.
Klik om te vergroten...

De elementen van de arrays zijn dus die woorden? (Of de characters van de woorden? Maar dat lijkt me niet.)
Vanwaar die score trouwens en niet gewoon een rechtstreekse vergelijking van woorden? Om toch een match te krijgen tussen woorden van dezelfde stam zoals wordt-worden, connect-connection? Zoja, dan zou ik eens kijken of je geen preprocessing kan doen met technieken uit text based information retrieval en natural language processing zoals porter stemming (http://tartarus.org/~martin/PorterStemmer/) en verwijdering van stopwoorden.
S

Sick-Boy

Legacy Member
NeverwinterX zei:
Mja de matrix is symmetrisch, daar had ik nog niet aan gedacht, dus dat kan je verder uitbuiten. En als er in de dynamische veel dezelfde elementen voorkomen, is het natuurlijk ook wat gemakkelijker dan allemaal aparte.



Link?
Klik om te vergroten...

Permutation - Wikipedia, the free encyclopedia

De elementen van de arrays zijn dus die woorden? (Of de characters van de woorden? Maar dat lijkt me niet.)
Vanwaar die score trouwens en niet gewoon een rechtstreekse vergelijking van woorden? Om toch een match te krijgen tussen woorden van dezelfde stam zoals wordt-worden, connect-connection? Zoja, dan zou ik eens kijken of je geen preprocessing kan doen met technieken uit text based information retrieval en natural language processing zoals porter stemming (Porter Stemming Algorithm) en verwijdering van stopwoorden.
Klik om te vergroten...

Het zijn inderdaad woorden en geen characters.
Preprocessing gebeurt, ik hou rekening met stopwoorden, Porter stemming en gebruik een NLP om veel van de woorden te elimineren. Maar de Porter stemmer is niet perfect. Als je connect en connection door dit algorithme haalt, zullen die een andere stam krijgen maar toch zijn ze ongeveer gelijk. Ook probeer ik rekening te houden met synoniemen (maar dat staat niet helemaal op punt).
Dus vandaar die vergelijking
N

NeverwinterX

Legacy Member
Sick-Boy zei:
Permutation - Wikipedia, the free encyclopedia
Klik om te vergroten...

Dat zegt dat de omzetting van de lehmer code van 1 permutatie naar die corresponderende permutatie in N log N kan. Maar om alle permutaties te berekenen met je dus eerst alle lehmer codes berekenen en dat is weer N! denk ik.

Sick-Boy zei:
Het zijn inderdaad woorden en geen characters.
Preprocessing gebeurt, ik hou rekening met stopwoorden, Porter stemming en gebruik een NLP om veel van de woorden te elimineren. Maar de Porter stemmer is niet perfect. Als je connect en connection door dit algorithme haalt, zullen die een andere stam krijgen maar toch zijn ze ongeveer gelijk. Ook probeer ik rekening te houden met synoniemen (maar dat staat niet helemaal op punt).
Dus vandaar die vergelijking
Klik om te vergroten...

Vreemd. Gebruik je de implementatie van die website die ik gaf? De java versie daar geeft connect en connection wel dezelfde stam.
S

Sick-Boy

Legacy Member
NeverwinterX zei:
Dat zegt dat de omzetting van de lehmer code van 1 permutatie naar die corresponderende permutatie in N log N kan. Maar om alle permutaties te berekenen met je dus eerst alle lehmer codes berekenen en dat is weer N! denk ik.



Vreemd. Gebruik je de implementatie van die website die ik gaf? De java versie daar geeft connect en connection wel dezelfde stam.
Klik om te vergroten...

Juist, ik had zelf een voorbeeld en dacht dat ik beter jouw voorbeeld kon gebruiken. Een verwarde geest in een verward lichaam :[.
Het is wel zo bij product(ion) en produc(e).
Ik krijg wel net een idee: misschien kan ik de lijst kleiner maken door alle combinaties te berekenen (N*M) en wanneer er voor een woord geen score hoger dan een threshold bestaat, schrap ik dat woord van de lijst.
S

Sick-Boy

Legacy Member
Ik heb het over een andere boeg gegooid en ben overgeschakeld naar het Stable Marriage probleem.
Ik heb de lijsten van woorden onderling gerangschikt volgens beste match. Vervolgens pik ik er per woord de beste (overblijvende) match uit. Zo bekom ik geen optimale oplossing, maar wel een benadering. Om de beste oplossing te vinden moet ik dan alle combinaties uitproberen. Mag ik veronderstellen dat de beste oplossing zich binnen een aantal suboptimale oplossingen bevindt? Dus dat na 1000 keer backtracken er geen betere oplossing meer zal uitkomen?

Weet iemand het algoritme van een gelimiteerde findall in prolog? :x
Het archief is een bevroren moment uit een vorige versie van dit forum, met andere regels en andere bazen. Deze posts weerspiegelen op geen enkele manier onze huidige ideeën, waarden of wereldbeelden en zijn op sommige plaatsen gecensureerd wegens ontoelaatbaar. Veel zijn in een andere tijdsgeest gemaakt, al dan niet ironisch - zoals in het ironische subforum Off-Topic - en zouden op dit moment niet meer gepost (mogen) worden. Toch bieden we dit archief nog graag aan als informatiedatabank en naslagwerk. Lees er hier meer over of start een gesprek met anderen.
Terug
Bovenaan