tjo

sitter och klurar på hur jag ska kunna optimera våran kod editor.
det jag vill göra är att matcha substrängar i en större sträng med maximal prestanda.

så tänkte kolla om någon av er har något bra förslag på algoritm som fixar det.



den nuvarande implementeringen fungerar såhär.

---------------
hämta 3 tecken från currentcharindex (pos i texten där vi vill matcha)

därefter använder jag dessa 3 tecken som nyckel i en hastabell för att hämta ut en array av ord som börjar på dessa 3 tecken.

(gör även samma sak med en 1 tecken lång nyckel för att matcha korta ord)


detta fungerar skapligt men ger dålig prestanda om många ord börjar på samma 3 tecken.
dessutom så är det inte helt snabbt att göra uppslag i en hashtabell.
----------------



min nuvarande ide' är att bygga ett träd med alla ordens tecken.
typ:
----------------
<code>
ordlista:
kalle
kruka
kula
arne
apa
arm

träd:


a k
p r a u r
a m n l l u
e l a k
e a

</code>
----------------


detta känns väl som det skulle fungera skapligt men det är ju alltid kul att kolla om det finns några andra förslag.

har även funderat på boyer moore men det fallar nog på att man har flera ord att söka på.

//Roger

Kan du inte använda Regular Expressions?
Det är nog det snabbaste sättet att manipulera strängar som är lite mer komplexa...

Mvh,
Thomas

Det ser ut som ett binärt träd tycker jag.

Kolla denna artikel

http://www.codeproject.com/vb/net/SimpleBTree.asp


Ola

nja , regex är faktiskt något av det slöare du kan använda , men det är bra på matcha komplexa patterns , men i mitt fall är det inga sånna , bara simpla strängar.

//Roger

binärträd har bara två undernoder , och i det här fallet skulle det betyda att jag får 16 noder i per nytt (unicode) tecken i trädet , det vill jag absolut inte ha.

_hur_ jag ska koda trädet är inte ett problem , frågan var om det finns andra smartare sätt att göra matchningarna (tex boyer moore , vilket kanske skulle fungera)

//Roger

Men ska strängarna bara börja på de bokstäverna du vill använda, eller kan de vara delar av dina strängar?
Boyer moore har väl ingen förtjänst när det bara gäller de första bokstäverna?

En variant jag har haft i huvet några månader utan att tänka mer på det är något i den här stilen (observera att det bara har varit en fundering, ingen analys eller något):
1.Du har delat in alla strängarna i tre olika "tabeller" (om vi struntar i terminologin en stund).
Den första tabellen är sorterad efter första bokstaven, andra efter andra, osv.

2. Sen tänker jag i C/C++-termer och tänker att du ger första bokstaven och får fram en pekare till motsvarande array hur lätt som helst, och sen motsvarande för andra och tredje arrayen.

Alltså om du har "def" som input så får du fram en pekare till en array med alla ord som börjar på "d", en pekare till en array för alla ord med "e" som andra bokstav osv.

Det hittills är ju skitlätt att göra och går grymt fort, eller hur?

3. Det sista steget skulle då vara att göra någon sorts matchning, där du bara sparar de som finns med i alla tre tabellerna. Det är där jag är osäker på om det finns snabba algoritmer och om du tjänar något på det. Om du kan få fram en snabb algoritm där så är det nog en metod som åtminstone har kapacitet att gå att tävla med din variant. Din verkar dock mycket lämplig.

Har du tid kan du ju gärna testa min idé och se om det är något att ha... =)

http://www-igm.univ-mlv.fr/~lecroq/string/ ser ut att vara en eventuellt intressant sida med strängmatchnings algoritmer + implementationer + java applet visualiseringar..

jag har börjat på en implementering som är ungefär som din.

jag har ett "TokenTree" som innehåller en 65536 poster stor "TokenNode" array
i denna array kan jag snabbt slå upp en TokenNode för ett visst unicode tecken. (första tecknet i orden jag vill matcha)

därefter kan jag traversera nodens childnoder tecken för tecken tills jag hittar en node som är flaggad som "end" node ... end noder behöer _inte_ vara den sista noden i en gren (tex i en gren med orden "hell" och "hello" så är båda hela ord även fast "o" är sista noden)
där efter fortsätter jag att traversera på samma sätt tills grenen tar slut , sedan returnerar jag den senast hittade endnoden

det här verkar fungera prima.

nästa problem är bara hur jag ska få in så den kan hitta både case sensitive och case insensitive tokens is samma träd.

behöver även kunna flagga att vissa ord kräver att det finns separator tecken på båda sidor om ordet.
(den här bör vara ganska simpel att fixa , matcha först , kolla om det finns separatorer efteråt)

//Roger

Jag var otydlig.. menade väl egentligen B-tree

http://www.semaphorecorp.com/btp/algo.html
http://www.brpreiss.com/books/opus6/html/page343.html#SECTION0011710000000000000000

Verkar inte vara en barnlek att implementera men det går väl.. ;)

så , nu får jag nog vara nöjd med implementeringen.
nu kan den tokenizera 1 000 000 rader kod på 1.3 sec

den slutliga rutinen fungerar såhär:

jag har en 65536 poster stor lookuptabell för första tecknet per ord
(obs det är en array med referencer så den äter inte _så_ mycket minne)

varje element index representerar då ett ascii/unicode värde.

så när jag scannar en sträng så tar jag ett tecken i min sträng , gör en lookup i den stora arrayen för att se om det finns några ord som börjar på det tecknet.

om det inte finns så fortsätter jag och gör samma sak med nästa tecken.

annars får jag tillbaka en trädnod som innehåller en 256 poster stor array
jag plockar nästa tecken från min sträng , andar med 255 och gör ett uppslag i den 256 poster stora arrayen.

fanns det inget där så var det ingen match , då börjar man om från början.
fanns det en nod i den arrayen så KANSKE det är en match , eftersom jag and'ar med 255 så kan noder för flera ascii tecken finnas på samma plats så jag får loopaigenom noden och dess syskonnoder (länkad lista) för att se om tecknet i strängen matchar tecknet i någon av noderna

fanns det en match så plockas nästa tecken i strängen och förra steget upprepas igen.


så jag är nöjd , det är iaf en 600 ggr snabbare än den gamla parsern (den som färgar kod här på pellesoft)



testade även att göra lite optimeringar a'la patricia tree (en nod kan hålla en sub sträng ,tex om trädet innehåller help och hello så kan startnoden innehålla "hel" med undernoderna "p" och "lo"

men av någon anledning gick det inte alls snabbare att parsa på det sättet (med c#)
min gissning är att det är för att .net gör bounds checkar när man accessar tecken för tecken i en sträng.

testade även med "unsafe" kod och pekare till tecknen , även det gick långsammare , så min gissning där är att det kostar lite cpu tid att gå in och ur unsafe block (?)

//Roger

<b>testade även med "unsafe" kod och pekare till tecknen , även det gick långsammare , så min gissning där är att det kostar lite cpu tid att gå in och ur unsafe block (?)</b>

Helt riktigt.
Ska du använda osäker i C# så bör du bara starta unsafeblocket en enda gång, förslagsvis i form av ett eget objekt.

Mitt förslag på lösning hade annars varit att bygga något som sorterar baserat på stränglängd i första steget, startbokstav i andra sedan ett btree. På så sätt har du rensat ut en stor del av de omöjliga träffarna redan efter steg två för att rensa bort så många möjliga träffar som möjligt så snart som möjligt är väl ändå det som ökar prestandan mest?

Osäker om detta har relevans i din fråga, men så här löste jag det i Vb för några år sedan.
<code>
Function BSearch(ByVal inLetters As String) As Boolean
'leta upp alla ord som börjar på 3 inLetters
Dim MidIndex As Long
Dim MinIndex As Long
Dim MaxIndex As Long
Dim sLen As Long
BSearch = False
MinIndex = 0
sLen = Len(inLetters)
'källan där alla ord finns lagrade
NewSearch:
MaxIndex = UBound(rsArray)
While MaxIndex >= MinIndex
MidIndex = (MinIndex + MaxIndex) / 2
If StrComp(inLetters, Left$(rsArray(MidIndex), sLen), 1) > 0 Then
MinIndex = MidIndex + 1
Else
If StrComp(inLetters, Left$(rsArray(MidIndex), sLen), 1) < 0 Then
MaxIndex = MidIndex - 1
Else
'Lägg in det hittade ordet i List1
List1.AddItem rsArray(MidIndex)
MinIndex = MidIndex + 1
'tillåter mig att använda GoTo här därför att det är effektivt
GoTo NewSearch
End If
End If
Wend
'sökning klar
BSearch = True
End Function
</code>

vid lite efterforskning så finns det ju tydligen namn på vad jag gjort :P

det är en DFA determenistic fenite automation och det är tyldigen samma sätt som alla parsers / compilers använder för att tokenizera kod.

//Roger