---

Jeg søger en algoritme til løsning af et strengsøgningsproblem.
Givet to strenge s1 og s2 ønsker jeg at finde den længste forekomst af
s1[0..n] i s2
s1=dette_er_det_vi_så
s2=det_var_i_går

længste match i s2 af længste startsekvens i s1 er "det_"
Problemet er at jeg ikke på forhånd ved at jeg skal søge efter "det_" i s1.
Måske skulle jeg søge efter "det_var". Det kan være den sekvens eksisterede
i s1.

En metode kunne være at sætte en mindste sekvenslængde på eksempelvis 3. Så
søger jeg efter "det" og finder den streng i s1. Den findes to steder. Jeg
noterer mig de to positioner som mulige løsninger og laver derefter en
simpel lineær sammenligning med resten af s2's start og de to kandidatsvar.
Den ene kandidat falder fra når jeg søger videre efter "_", mens den anden
også passer der. Den sidste løsning falder fra ved søgning efter "v" og
længste svar var altså den sidstoverlevende kandidat. Jeg antager
umiddelbart at der findes en mere fiks metode, som er mindre hæmmet af
strenge som giver rigtig mange kandidater.

Jeg håber at jeg har spurgt klart nok. Hvis ikke, så skal jeg gerne forsøge
igen.

---

"Jakob Nielsen" <a@b.c> skrev i en meddelelse
news:429f5819$0$67264$157c6196@dreader2.cybercity.dk...
> Jeg søger en algoritme til løsning af et strengsøgningsproblem.
> Givet to strenge s1 og s2 ønsker jeg at finde den længste forekomst af
> s1[0..n] i s2
> s1=dette_er_det_vi_så
> s2=det_var_i_går
>
> længste match i s2 af længste startsekvens i s1 er "det_"
> Problemet er at jeg ikke på forhånd ved at jeg skal søge efter "det_" i
> s1. Måske skulle jeg søge efter "det_var". Det kan være den sekvens
> eksisterede i s1.
>
> En metode kunne være at sætte en mindste sekvenslængde på eksempelvis 3.
> Så søger jeg efter "det" og finder den streng i s1. Den findes to steder.
> Jeg noterer mig de to positioner som mulige løsninger og laver derefter en
> simpel lineær sammenligning med resten af s2's start og de to
> kandidatsvar. Den ene kandidat falder fra når jeg søger videre efter "_",
> mens den anden også passer der. Den sidste løsning falder fra ved søgning
> efter "v" og længste svar var altså den sidstoverlevende kandidat. Jeg
> antager umiddelbart at der findes en mere fiks metode, som er mindre
> hæmmet af strenge som giver rigtig mange kandidater.
>
> Jeg håber at jeg har spurgt klart nok. Hvis ikke, så skal jeg gerne
> forsøge igen.

Det minder lidt om at sortere spektraldata. Er det hurtigere at finde
bogstavet i din sub-string med fx den højeste char-kode, finde det tilsvare
char i hoved-strengen og søge til højre og venstre?
Det virker umiddelbart enkelt at tage det første bogstav i din substring og
søge efterfølgende bogstaver, hvis der er et hit i hovedstrengen. Det går
progressivt fremad, og du har sikkert en løsning efter et enkelt gennemløb.

Carsten

---

> Det minder lidt om at sortere spektraldata.

Det kender jeg så intet til :-/

> Er det hurtigere at finde bogstavet i din sub-string med fx den højeste
> char-kode, finde det tilsvare char i hoved-strengen og søge til højre og
> venstre?

Det forstår jeg vist ikke helt. Hvad skulle formålet være? I eksemplet skal
den fundne match starte med d. Hvis sådan et match findes, så kan det
forbedres hvis det efterfølges af et e. Hvis sådan et findes, så kan det
forbedres hvis det e følges af et t etc.

> Det virker umiddelbart enkelt at tage det første bogstav i din substring
> og søge efterfølgende bogstaver, hvis der er et hit i hovedstrengen. Det
> går progressivt fremad, og du har sikkert en løsning efter et enkelt
> gennemløb.

Problemet med den metode er at den potentielt kan være ret langsom.
Hvis vi antager at jeg finder et match på position p0 og matchet fortsætter
til p100 og derefter fejler, så er det muligt at der faktisk findes en match
på pn hvor 0<n<100. Man skal altså potentielt hoppe helt tilbage og starte
søgningen på p1 igen. Det vil virke og det vil være frygtelig langsomt. I
værste tilfælde vil det kræve (n-m)*m sammenligninger hvor n er længden af
s1 og m er længden af s2.

et eksempel på en sådan situation er
s1=aaaaaaaaaabbbbbbbbbb
s2=aaaaaaaaabbbbbbbbbb
Bedste match er en position inde i s1 hvor man kan matche hele s2. Hvis du
søger sekventielt, så vil du se et muligt match på position 0 og det
fortsæter med at være et godt match helt frem til første b i s2, hvor s1
stadig har et a.
Du misser det gode match hvis du bare fortsætter søgningen hvor den forrige
fejlede.
Man skal helt tilbage og starte på position 1 for at finde det bedste match.

Strengsøgning har udmærkede metoder til at søge efter en given streng i en
anden streng, men her skal jeg finde det længste præfiks.

Jeg søger en hurtig metode.

---

"Jakob Nielsen" <a@b.c> skrev i en meddelelse
news:429f73dc$0$67258$157c6196@dreader2.cybercity.dk...
>> Det minder lidt om at sortere spektraldata.
>
> Det kender jeg så intet til :-/
>
>> Er det hurtigere at finde bogstavet i din sub-string med fx den højeste
>> char-kode, finde det tilsvare char i hoved-strengen og søge til højre og
>> venstre?
>
> Det forstår jeg vist ikke helt. Hvad skulle formålet være? I eksemplet
> skal den fundne match starte med d. Hvis sådan et match findes, så kan det
> forbedres hvis det efterfølges af et e. Hvis sådan et findes, så kan det
> forbedres hvis det e følges af et t etc.

Det character set som jeg kan checke (Microsoft Office), har kodenummer fra
0-255, men de vanlige bogstaver og tal er grupperet sådan at du fx kan søge
om din sub-string har et tegn med en kode der ligger ud over 48-122, for så
er det ikke et tegn som forekommer i gængse tekster. Fra 57-65 og 90-97 er
der også en lille gruppe usædvanlige tegn. Måske kan det endog betale sig at
søge i gruppen af store bogstaver(65-90) før små, men det kan du selv
vurdere ud fra forventningen om de tekster der skal undersøges.
Så hvis du starter med at skanne din substring for usædvanlige tegn
minimerer du forkerte hits der skal undersøges for at nå i mål. Det er jo
godt, HVIS der er atypiske tegn. Jeg kan ikke vurdere om det kan betale sig
at give de gængse tegn din egen kode, hvor du fx tildeler lave værdier til
meget brugte bogstaver, og så starter med at skanne de største.

Carsten

---

> Så hvis du starter med at skanne din substring for usædvanlige tegn
> minimerer du forkerte hits der skal undersøges for at nå i mål. Det er jo
> godt,

Jeg skulle nok have kaldt det en vektor for ikke at forvirre med hensyn til
tekst. Normalt går den slags dog under navnet "strengsøgning/"string
matching".
Det er data jeg søger i og som udgangspunkt er alle værdier lige sansynlige

---

Jakob Nielsen wrote:
> Jeg søger en algoritme til løsning af et strengsøgningsproblem.
> Givet to strenge s1 og s2 ønsker jeg at finde den længste forekomst af
> s1[0..n] i s2

Det minder temmelig meget om "Længste fælles delstreng"-problemet.
I dit tilfælde skal den ene delstreng dog være et præfiks af s1.

Mon ikke dynamisk programmering kan bruges. Se en løsning
til længste fælles delstreng her:

<http://www.ics.uci.edu/~dan/class/161/notes/6/Dynamic.html>

--
Jens Axel Søgaard

---

Det minder temmelig meget om "Længste fælles delstreng"-problemet.
I dit tilfælde skal den ene delstreng dog være et præfiks af s1.

Ja det minder om, men længste fælles delstreng tager ikke hensyn til tegn
imellem.
dette_er_en_test
og
dQettQe_er
har jo længste fælles streng som dette_er selvom der er Q stukket ind i den.
Jeg har overvejet den løsning, men kan ikke se hvordan algoritmen kan
modificeres. Måske du har et bud i den retning?

---

"Jakob Nielsen" <a@b.c> writes:

> Ja det minder om, men længste fælles delstreng tager ikke hensyn til tegn
> imellem.
> dette_er_en_test
> og
> dQettQe_er
> har jo længste fælles streng som dette_er selvom der er Q stukket ind i den.

Jeg tror du kigger på den forkerte algoritme. Prøv at søge efter

Longest common substring problem

på den side Jens refererede til.

--
Ole Laursen
http://www.cs.aau.dk/~olau/

---

> Jeg tror du kigger på den forkerte algoritme. Prøv at søge efter
>
> Longest common substring problem
>
> på den side Jens refererede til.

Ja, jeg læste det som længste del-sekvens og ikke del-streng. Det ser mere
rigtigt ud. Kendte egentlig godt metoden, men droppede den i sin tid (for
nogle år siden da jeg rodede med det samme), fordi mine strenge er lidt
store, og man skal opbygge en n*m matrix med hver celle stor nok til at
rumme største mulige strenglængde.

Det fylder godt nok i hukommelsen, men måske det er muligt.

Hvad hvis mine "strenge" er på eksempelvis 64k hver? Findes der en variant
af algoritmen til den slags størelser? Det vil jo kræve 64k*64k*16b = ca.
8GB

Jeg har en ide om at man kan behandle strengene i mindre bidder i første
omgang og finde gode kandidater, men kan ikke helt se hvordan.

---

Scripsit "Jakob Nielsen" <a@b.c>

> Jeg søger en algoritme til løsning af et strengsøgningsproblem.
> Givet to strenge s1 og s2 ønsker jeg at finde den længste forekomst af
> s1[0..n] i s2
> s1=dette_er_det_vi_så
> s2=det_var_i_går

> længste match i s2 af længste startsekvens i s1 er "det_"
> Problemet er at jeg ikke på forhånd ved at jeg skal søge efter "det_" i s1.
> Måske skulle jeg søge efter "det_var". Det kan være den sekvens eksisterede
> i s1.

Jeg ville gøre følgende. Lad K være længden af svaret. En almindelig
hurtig strengsøgningsalgoritme (fx Boyer-Moore) kan give dig svaret på
"er K >= n?" for et givet n. Brug den som subrutine idet du skyder dig
ind på K ved bisektion.

Så vidt jeg lige kan ræsonnere mig frem til burde den metode have
lineær køretid (!) i gennemsnitstilfældet, idet Boyer-Moore bliver
hurtigere desto længere den streng man søger efter er. (Skjult
antagelse: s2 er trods alt kort nok til at tegn på vilkårlige
positioner kan tilgås i konstant tid).

--
Henning Makholm "I can get fat! I can sing!"

---

> Jeg ville gøre følgende. Lad K være længden af svaret. En almindelig
> hurtig strengsøgningsalgoritme (fx Boyer-Moore) kan give dig svaret på
> "er K >= n?" for et givet n. Brug den som subrutine idet du skyder dig
> ind på K ved bisektion.

Så du vil eksempelvis sætte n=a og se om du kan finde et match i s1 for de a
første tegn i s2?
Hvis du ikke kan, så ved du at der ikke er et match som er større end a, og
du vil derefter forsøge med a/2. Hvis det lykkes, så er der muligvis et svar
mellem a/2 og a, og sådan søger du ned usikkerhed?
Det er egentlig en meget simpel og elegant metode.

Ja, køretiden må vel være lineær, da strengsøgningen kan udføres lineært og
valget af n er uafhængigt af strenglængderne. Den er så bare lineær med høj
tidsværdi, ved nærmere eftertanke.

---

Scripsit "Jakob Nielsen" <a@b.c>

>> Jeg ville gøre følgende. Lad K være længden af svaret. En almindelig
>> hurtig strengsøgningsalgoritme (fx Boyer-Moore) kan give dig svaret på
>> "er K >= n?" for et givet n. Brug den som subrutine idet du skyder dig
>> ind på K ved bisektion.

> Så du vil eksempelvis sætte n=a og se om du kan finde et match i s1 for de a
> første tegn i s2?
> Hvis du ikke kan, så ved du at der ikke er et match som er større end a, og
> du vil derefter forsøge med a/2. Hvis det lykkes, så er der muligvis et svar
> mellem a/2 og a, og sådan søger du ned usikkerhed?

Ja.

> Det er egentlig en meget simpel og elegant metode.

Morale: En sjælden gang imellem kan det ikke betale sig at forsøge at
være smart og nå at søge efter flere præfikser i s1 i et enkelt
gennemløb.

> Ja, køretiden må vel være lineær, da strengsøgningen kan udføres lineært og
> valget af n er uafhængigt af strenglængderne.

Jeg ville bruge en helt generel bisektion hvor jeg starter med at
sætte nedre grænse til 0 og øvre grænse til længden af s2 (som du vist
kaldte s1 i første indlæg, eller er jeg forvirret). Første forsøg
bliver dermed til den halve længde.

> Den er så bare lineær med høj tidsværdi, ved nærmere eftertanke.

Egentlig ikke. Med Boyer-Moore er søgning efter lange delstrenge i
gennemsnit hurtigere end søgning efter kortere: At søge efter en
dobbelt så lang streng går dobbelt så hurtigt. Så selv om det viser
sig at det længste præfiks har længde 0 (det værste tilfælde: første
tegn i s2 forekommer slet ikke i s1), vil hele operationen ikke tage
længere tid end at lede efter første tegn i s2 i en streng der er
dobbelt så lang som s1.

Eller rettere ... der er vist klippet et par hjørner i den
asymptotiske analyse, så "dobbelt så lang" skal måske i stedet være
"fire eller fem gange så lang". Stadig ikke en kompleksitet der virker
afskrækkende.

Med forbehold for at jeg ikke kan huske hvor lang tid Boyer-Moore's
indledende tabelkonstruktion tager, men jeg tror også det er lineært
eller tæt på lineært.

--
Henning Makholm "We can hope that this serious deficiency will be
remedied in the final version of BibTeX, 1.0, which is
expected to appear when the LaTeX 3.0 development is completed."

---

Jakob Nielsen wrote:
> Jeg søger en algoritme til løsning af et strengsøgningsproblem.
> Givet to strenge s1 og s2 ønsker jeg at finde den længste forekomst af
> s1[0..n] i s2
> s1=dette_er_det_vi_så
> s2=det_var_i_går
>
> længste match i s2 af længste startsekvens i s1 er "det_"
> Problemet er at jeg ikke på forhånd ved at jeg skal søge efter "det_" i s1.
> Måske skulle jeg søge efter "det_var". Det kan være den sekvens eksisterede
> i s1.
>

Hvad der er hurtigst afhænger jo af mange ting. Længde af s1 hhv. s2,
hvor mange match der er i s2 på dele af s1, længden af disse match,
hvor mange match der overlapper og længden af disse overlap.

Med lange s1 og s2 og mange overlappende match (med lange overlap), så
vil det hurtigste være, at lade dit program først konstruere en
tilstandsmaskine der genkender s1. Så skal du bare køre s2 gennem
tilstandsmaskinen og således se på hver posistion i s2 én gang.
Kompleksiteten i denne løsning er altså længde(s1) + længde(s2).

Med korte s1 og s2 kan du jo anvende stort set hvilken som helst simpel
metode. F.eks. finde første forekomst af s1(0) i s2, og finde længden
af det match der starter her. Find hefrefter næste forekomst af s1(0)
i s2 og find længden af matchet startende her, og så fremdeles
(KISS).

J.O.