---

Hej gruppe.

Jeg har fundet en del på nettet om algoritmer der beregner længden af
longest common subsequence, men problematikken drejer sig altid om to
strenge.

Jeg har en opgave, hvor jeg ønsker at lave noget lignende en
stavekontrol, dvs. en database med mange strenge og én streng som skal
matches mod dem alle. Jeg skal have returneret dem der ligner mest og i
sorteret rækkefølge.

Den måde jeg udregner hvor ens to strenge er (S) angivet i intervallet
[0-1] - LCS angiver længden af longest common subsequence:
S(a, b) = LCS(a, b) * 2 / (length(a) + length(b))

Hvis jeg vil finde match på 80% f.eks., så gælder:
S(a, b) > 0,8 =>
LCS(a, b) * 2 / (length(a) + length(b)) > 0,8 <=>
LCS(a, b) > 0,8 * (length(a) + length(b)) / 2

Da LCS højst er længden af den mindste streng (a, b) kan jeg nu
afgrænse de længder af strenge jeg skal søge i min database. Det kan
nemt gøres med et indeks på strengenes længder.

Problemet kommer alligevel. For hvad med de sidste mange strenge. Kan
man optimere algoritmen til at udregne LCS, når det kun er længden
man skal bruge? Og kan man gøre det effektivt for mange strenge eller
skal man bruge en brute force metode og køre algoritmen for alle
strenge man skal søge igennem?
Jeg tænker f.eks. på om der er nogle sammenhænge for LCS med tre
strenge (a, b, c) eller måske flere, som gør at har man fundet LCS(a,
b) og LCS(b, c), så kan man måske sige noget om LCS(a, c), eller
lignende optimeringer.

Jeg har ikke været heldig nok til at finde noget om LCS i databaser
på nettet, så håber der er nogle behjælpelige sjæle her.

P.S.: Hvordan gør stavekontrollen? Jeg kunne forestille mig de bruger
fonetiske indeks i stedet for.

Mvh.
Bjarke W.

---

Prøv at søge på algoritmerne Levenshtein og Ratcliff/Obershelp, som
sammenligner 2 tekststrenge og beregner hvor meget de ligner hinanden. De er
begge mere avancerede end LCS, som du beskriver nedenfor. De kræver dog
fortsat, at man beregner udtrykket for hver streng i databasen og ikke på et
helt datasæt, som du ønsker.

Måske ikke lige det du er ude efter, men det kan måske bruges alligevel.

hilsen
Uffe



"Bjarke Walling Petersen" <bjarke.walling@gmail.com> wrote in message
news:1135199829.230173.154540@g47g2000cwa.googlegroups.com...
Hej gruppe.

Jeg har fundet en del på nettet om algoritmer der beregner længden af
longest common subsequence, men problematikken drejer sig altid om to
strenge.

Jeg har en opgave, hvor jeg ønsker at lave noget lignende en
stavekontrol, dvs. en database med mange strenge og én streng som skal
matches mod dem alle. Jeg skal have returneret dem der ligner mest og i
sorteret rækkefølge.

---

Bjarke Walling Petersen wrote:
> Hej gruppe.
>
> Jeg har fundet en del på nettet om algoritmer der beregner længden af
> longest common subsequence, men problematikken drejer sig altid om to
> strenge.
>
> Jeg har en opgave, hvor jeg ønsker at lave noget lignende en
> stavekontrol, dvs. en database med mange strenge og én streng som skal
> matches mod dem alle. Jeg skal have returneret dem der ligner mest og i
> sorteret rækkefølge.
>
> Den måde jeg udregner hvor ens to strenge er (S) angivet i intervallet
> [0-1] - LCS angiver længden af longest common subsequence:
> S(a, b) = LCS(a, b) * 2 / (length(a) + length(b))
>
> Hvis jeg vil finde match på 80% f.eks., så gælder:
> S(a, b) > 0,8 =>
> LCS(a, b) * 2 / (length(a) + length(b)) > 0,8 <=>
> LCS(a, b) > 0,8 * (length(a) + length(b)) / 2
>
> Da LCS højst er længden af den mindste streng (a, b) kan jeg nu
> afgrænse de længder af strenge jeg skal søge i min database. Det kan
> nemt gøres med et indeks på strengenes længder.
>
> Problemet kommer alligevel. For hvad med de sidste mange strenge. Kan
> man optimere algoritmen til at udregne LCS, når det kun er længden
> man skal bruge? Og kan man gøre det effektivt for mange strenge eller
> skal man bruge en brute force metode og køre algoritmen for alle
> strenge man skal søge igennem?
> Jeg tænker f.eks. på om der er nogle sammenhænge for LCS med tre
> strenge (a, b, c) eller måske flere, som gør at har man fundet LCS(a,
> b) og LCS(b, c), så kan man måske sige noget om LCS(a, c), eller
> lignende optimeringer.
>
> Jeg har ikke været heldig nok til at finde noget om LCS i databaser
> på nettet, så håber der er nogle behjælpelige sjæle her.
>
> P.S.: Hvordan gør stavekontrollen? Jeg kunne forestille mig de bruger
> fonetiske indeks i stedet for.
>
> Mvh.
> Bjarke W.

Hej

Kan du forklare lidt mere om hvad det skal anvendes til? Jeg har engang
arbejdet med noget der ligner, så måske kan jeg hjælpe.

Hvis du skal finde strenge der ligner, er du så sikker på, at det
ikke ville være bedre at arbejde med mindste editeringsafstand end med
LCS.

Jens Olsen

---

> Prøv at søge på algoritmerne Levenshtein og Ratcliff/Obershelp, som ...
Det vil jeg prøve. Har søgt en lille smule på levenshtein, men synes
heller ik jeg fandt noget der virkelig hjælper, udover et eneste
firma, som sælger en databaseløsning, der kan matche en streng mod
2,5 mio. på 0,1 sekund (skriver de). Men det koster sikkert kassen, og
nu sidder vi jo og udvikler det her system selv - det er også meget
sjovere og man lærer mere.
I øvrigt kan jeg lave match på alle vejnavne i Danmark (kun 115.000)
uden optimeringer på ca. 0,5 sekund.. den skal gerne blive en del
mindre. Jeg ville lige skrive her på gruppen inden jeg begynder at
lave de smarte optimeringer, hvis der nu er noget der er endnu
smartere.

Er dog kommet frem til at man måske kan udelukke strenge "intelligent"
i en løsning med levenshtein. Hvis jeg kalder funktionen L, så må
der jo gælde:
L(a, c) <= L(a, b) + L(b, c) [Afstanden fra a til c er højst lig
afstanden fra a til b til c]
Og man ved at:
L(a, b) <= max(length(a), length(b))
Den værste situation at komme fra a til b er at ændre alle tegn i den
mindste streng og så sætte de sidste tegn til, dvs. en afstand
svarende til den længste streng.

Ud fra de to uligheder kan man måske lave nogle afgrænsninger på
strenge man endnu ikke har matchet og se om de er interessante, dvs. om
de matcher med mere eller mindre end en given procent. Men det er
umiddelbart rimelig komplekst hvordan man bygger det system op, synes
jeg.

Mvh.
Bjarke W.

---

Hej Jens Olsen.

Jeg synes jeg allerede har svaret på dit indlæg, men da min eneste
news reader er Google i øjeblikket, så har jeg vist lidt
startvanskeligheder :)

Prøver igen (så det skal ik undre nogen hvis der kommer to svar):

jenspolsen@hotmail.com skrev:
> Kan du forklare lidt mere om hvad det skal anvendes til? Jeg har engang
> arbejdet med noget der ligner, så måske kan jeg hjælpe.
Det skal bruges til et system der kan validere adresser og foreslå et
bedste match om muligt, hvis adressen ikke findes eksakt. Den skal
køre mange adresser igennem, så det må gerne gå relativ hurtigt.

> Hvis du skal finde strenge der ligner, er du så sikker på, at det
> ikke ville være bedre at arbejde med mindste editeringsafstand end med
> LCS.
Jeg har overvejet andre, jo, men skal vist lige læse lidt mere om dem
på nettet først. Hvis de har en større tidskompleksitet, så er jeg
jo ikke ligefrem hjulpet mht. hastighed.

Jeg vil prøve at søge lidt på de algoritmer Uffe skrev om.

Mvh.
Bjarke W.

---

> Kan du forklare lidt mere om hvad det skal anvendes til? Jeg har engang
> arbejdet med noget der ligner, så måske kan jeg hjælpe.
Det er et system, som kan validere adresser og foreslå bedste match om
muligt, hvis adressen ikke findes eksakt. Systemet skal kunne køre
mange adresser igennem relativ hurtigt.

> Hvis du skal finde strenge der ligner, er du så sikker på, at det
> ikke ville være bedre at arbejde med mindste editeringsafstand end med
> LCS.
Jo, du har muligvis ret. Indtil videre har vi brugt LCS og jeg må da
indrømme at der er nogle gange at den ik virker særlig godt, så
måske levenshtein eller en anden algoritme. Men har de ikke en større
tidskompleksitet? Ok, jeg må søge lidt på nettet igen :)

Mvh.
Bjarke W.

---

Bjarke Walling Petersen wrote:

> Problemet kommer alligevel. For hvad med de sidste mange strenge. Kan
> man optimere algoritmen til at udregne LCS, når det kun er længden
> man skal bruge?

Det tror jeg ikke - man er jo nødt nødt at kende de enkelte tegn
for den faste streng under udregningen.

> Og kan man gøre det effektivt for mange strenge eller
> skal man bruge en brute force metode og køre algoritmen for alle
> strenge man skal søge igennem?

Måske - men jeg tror det er ikke-trivielt.

> P.S.: Hvordan gør stavekontrollen? Jeg kunne forestille mig de bruger
> fonetiske indeks i stedet for.

Måske kan du bruge

<http://xldb.fc.ul.pt/data/Publications_attach/spellcheck.pdf>
?

til at få nogle ideer fra. De bruger en kombination af en trie og
et søgetræ. De ord der oftest søges på vil med tiden vandre til
toppen af træet (hvis jeg har forstået det ret).

Eneste problem med artiklen, er at der mangler en forklaring af
hvordan de laver opslagene i deres datastruktur.

--
Jens Axel Søgaard

---

Jens Axel Søgaard skrev:
> Bjarke Walling Petersen wrote:
> > Og kan man gøre det effektivt for mange strenge eller
> > skal man bruge en brute force metode og køre algoritmen for alle
> > strenge man skal søge igennem?
>
> Måske - men jeg tror det er ikke-trivielt.

Nej, det er jeg efterhånden også ved at indse.

> > P.S.: Hvordan gør stavekontrollen? Jeg kunne forestille mig de bruger
> > fonetiske indeks i stedet for.
>
> Måske kan du bruge
>
> <http://xldb.fc.ul.pt/data/Publications_attach/spellcheck.pdf>

Det ser meget spændende ud. Men må indrømme at jeg ikke er så meget
inde i datastrukturer. Hvordan indsætter man en streng i et trie? For
som de har det så er der tre subnoder til hver node og kun den ene er
for eksakt match af bogstavet. Hvordan indsætter man f.eks. strengene
"en" og "et", når 'n' og 't' skal deles om en node.

> til at få nogle ideer fra. De bruger en kombination af en trie og
> et søgetræ. De ord der oftest søges på vil med tiden vandre til
> toppen af træet (hvis jeg har forstået det ret).

Det har jeg ikke helt forstået endnu, men jeg vil prøve at læse den
igen og se om jeg kan finde mere information om det på nettet.

> Eneste problem med artiklen, er at der mangler en forklaring af
> hvordan de laver opslagene i deres datastruktur.

Har jeg heller ikke fundet ud af :/

Men tak for artiklen. Jeg har allerede fundet mange nye ord jeg skal
søge på nettet omkring stavekontroller og algoritmer. Jeg synes blot
at det meste man finder er afhandlinger skrevet af forskere eller
studerende på de sidste år med indforståede titler, og ikke noget
der er særlig tilgængeligt for en "sølle" 1.-årsstuderende som mig.
Der er f.eks. meget lidt på Wikipedia, men jeg tager det som en
udfordring. Bare utroligt at der ikke er skrevet mere om
stavekontroller generelt, synes jeg (og måske er det fordi jeg ikke
kender de rigtige udtryk).

Mvh.
Bjarke W.

---

Bjarke Walling Petersen wrote:
> Jens Axel Søgaard skrev:

>>Måske kan du bruge
>>
>> <http://xldb.fc.ul.pt/data/Publications_attach/spellcheck.pdf>
>
>
> Det ser meget spændende ud. Men må indrømme at jeg ikke er så meget
> inde i datastrukturer. Hvordan indsætter man en streng i et trie? For
> som de har det så er der tre subnoder til hver node og kun den ene er
> for eksakt match af bogstavet. Hvordan indsætter man f.eks. strengene
> "en" og "et", når 'n' og 't' skal deles om en node.

En almindelig trie er er forgrenet træ, hvor hver kant er mærket med
et tegn. Tegnene på rodens udkanter repræsenterer det første bogstav
i en streng. Udkanter fra børn af roden repræsenterer andet bogstav
og så videre. I et blad angives endelsen af ordet.

For eksempel repræsenterer denne trie,

/|\
/ | \
/ | \ ø
/ | \
a / | l
/ b|
/ \ |\
f / d | \
/ i| \o
stand | \
/\ gstav
ster l

ordene: "afstand", "ad", "bister", "bil", "bogstav" og "øl".

Se også: <http://en.wikipedia.org/wiki/Trie>.

I stedet for at have træer med mange forgreninger, kan man
lave tricket i artiklen med at lade dele op i "lister" vha
den tredje gren.

>>til at få nogle ideer fra. De bruger en kombination af en trie og
>>et søgetræ. De ord der oftest søges på vil med tiden vandre til
>>toppen af træet (hvis jeg har forstået det ret).
>
> Det har jeg ikke helt forstået endnu, men jeg vil prøve at læse den
> igen og se om jeg kan finde mere information om det på nettet.
>
>>Eneste problem med artiklen, er at der mangler en forklaring af
>>hvordan de laver opslagene i deres datastruktur.
>
> Har jeg heller ikke fundet ud af :/

Måske slår de bare op mange gange - opslag er billigt i en trie.

> Men tak for artiklen. Jeg har allerede fundet mange nye ord jeg skal
> søge på nettet omkring stavekontroller og algoritmer. Jeg synes blot
> at det meste man finder er afhandlinger skrevet af forskere eller
> studerende på de sidste år med indforståede titler, og ikke noget
> der er særlig tilgængeligt for en "sølle" 1.-årsstuderende som mig.
> Der er f.eks. meget lidt på Wikipedia, men jeg tager det som en
> udfordring. Bare utroligt at der ikke er skrevet mere om
> stavekontroller generelt, synes jeg (og måske er det fordi jeg ikke
> kender de rigtige udtryk).

Jeg kunne heller ikke finde noget - men det skulle undre mig, om
der ikke var noget et sted.

--
Jens Axel Søgaard

---

Bjarke Walling Petersen fortalte:

> Der er f.eks. meget lidt på Wikipedia, men jeg tager det som en
> udfordring.

Men der er et digt, så kom ikke og sig at datalogi ikke er poetisk:

Eye halve a spelling chequer,
It came with my pea sea,
It plainly marques four my revue
Miss steaks eye kin knot sea.

Iøvrigt ville jeg da først studere de typiske fejl i adresser, hvis det
kun er det din stavekontrol skal bruges til.

Mvh
Martin
--
Det er ligegyldigt hvad folk siger om mig, - selv hvis det er pænt