On 18 May 98 at 14:20,   > wrote:
> Elore magadott sztringeket keresunk egy input karaktersorozatban. Most
> eppen az "abc"-t es a "bcde" -t. Csinalunk harom bitvektort ( S, E, U ),
> meg egy bitmatrixot ( M ) az alabbi tartalommal:
[...stb...]
Aha!
Dömölki Bálint-ot ismerem (egy idoben a fonokom volt), de nem tudtam,
hogy ez az algoritmus róla van elnevezve. En ezt Shift-search (vagy
shift-and) algoritmusnak ismertem. A Byte magazin illetve az MSJ irt
rola 5-6 eve, de kicsit bele kellett nyulnom, mert (szerintem) rossz
volt a programjuk :)
Kicsit egyszerubben es gyakorlatiasabban is meg lehet fogalmazni, ha
nem akarunk egyszerre tobb dolgot keresni, hanem csak egyetlent:
Tegyuk fel, hogy max 32 betu hosszusagu stringet akarunk keresni:
ekkor a keresest vegezhetjuk egy 32 bites hosszu (tehat egyetlen
regiszterben elfero) keresovektorral. Fel kell epiteni egy 256 elemu,
elemenkent 32 bites Characteristic Vector Table-t (CV tabla), ez itt
a neve a Domolki fele M matrixnak. Ebben a tablazatban minden
betuhoz azokban a bitekben van 1-es, amilyen poziciokban elofordulhat
az adott betu. A keresovektorban (regiszterben) azokon a
bitpoziciokon lesz 1-es, ameddig mar egyezett a keresett string.
Amikor elovesszuk a kovetkezo byte-ot, akkor egyreszt shift-elunk
egyet a keresovektorral, es lemaszkoljuk a CV tabla byte-adik
elemevel, hogy kideruljon, folytatodik-e ezzel a byte-tal valamelyik
eddigi substring. Ezen kivul hozza-or-oljuk a CV tabla byte-adik
elemenek elso bitjet, mert hatha indul ezzel a byte-tal uj substring.
Ha egy bit el tud erni a keresett string hosszaig, akkor talaltunk
egy egyezest.
Maga a program olyan rovid, hogy idemasolom. A programom 16
bites, DOS ala irtam, de legalabb 386-os proci kell hozza, mert
hasznal 32 bites regisztert is. Konnyen lehet belole 32 bites flat
mod-ut is csinalni. Elol all az a rutin, ami egy stringhez
megcsinalja a CV tablat, majd maga a kereses:
BuildCVTable proc far
; DS:SI= keresendo string
; CX= string hossza = 1..32 (nincs ellenorzes)
; ES:DI= CV Table (Characteristic Vector Table) 256*4byte hosszu
; ES:DI es CX nem romlanak (At kell oket adni ShiftSearch szamara is)
; a CV tablaban minden kodhoz (0..255) egy 32bites bejegyzes tartozik
; ami leirja, hogy a keresendo stringben melyik poziciokon fordulhat
; elo a kod
push cx
push di
cld
xor ax,ax
mov cx,256*4/2
rep stosw
pop di
pop cx
push cx
mov edx,80000000h
bcvt1:
xor bh,bh
mov bl,[si]
inc si
shl bx,2
or es:[di+bx],edx
shr edx,1
loop bcvt1
pop cx
ret
BuildCVTable endp
; Shift-AND algoritmus (Udi Manber & Sun Wu) Byte 1992 nov.
; Exact Match
ShiftSearch proc far
; DS:SI= szoveg, amiben keresni kell
; BX= szoveg hossza
; ES:DI= CVTable (BuildCVTable =in=out)
; CX= keresendo string hossza 1..32 (BuildCVTable =in=out)
;
; ki CY= nc, ha talalt
; DS:SI= a talalt szoveg moge mutat
;
xor edx,edx
stc
rcr edx,cl ; leallunk ilyen hossz utan
; '93 april Q&A
;;;;;;; mov ecx,80000000h ; egyezo string hossza MSJ szerint!
xor ecx,ecx ; egyezo string hossza szerintem
test bx,bx
jz fstV ; ures stringben kellene keresni?
xor eax,eax
movzx edi,di
fstS: ; ciklus
lodsb
; elozo sub-stringek novekszenek tovabb, ha lehet:
; (ecx >> 1) and cv
; valamint kezdodhet egy 1 hosszusagu sub-string:
; or (80000000 and cv)
;
stc ; 80000000 lesz. Kezdodhet pl. itt egy match
rcr ecx,1 ; es folytatodhat egy megkezdett match
and ecx,es:[edi+4*eax] ; ez a betu lehet-e
; ez(ek)en a hely(ek)en
test ecx,edx
jnz fstFound ; teljes hosszusagban jo volt!
dec bx
jnz fstS
fstV:
stc
ret
fstFound:
clc
ret
ShiftSearch endp
Az algoritmus elonye nem a gyorsasaga (ennel van sokkal gyorsabb
string kereso), hanem az, hogy csupan a CV tabla modositasaval lehet
vele 'joker'-es keresest csinalni, tehat olyat, hogy pl. a string
valamelyik betuje barmi lehet, illetve pl. barmilyen nagybetu, vagy
barmilyen szamjegy, stb. Egyszeruen minden olyan byte-hoz
engedelyezni kell az adott pozicio bitjet is a CV tablaban. Persze
ehhez masmilyen BuildCVTable rutint kell irni, ha mondjuk ilyen
regular expression szintaktikaval akarjuk ezt leirni:
a.c[0-9]d[^EFG]
Azt viszont program modositas nelkul, csak a CV tablaval mar _nem_
erhetjuk el, hogy a regular expression * -jat is kezelje, ami
akarmilyen hosszu string-re illeszkedik. Alternativak kereseset
viszont (amirol z2 is irt) pici programmodositassal lehet elerni: A
'string kezdodik' or-olast, meg a 'string vege' feltetelt kell csak
modositani, es maradhat minden ugyanigy, ha a ket vagy tobb
alternativa egyuttes hossza nem tobb 32-nel.
Fontos erdekessege meg az algoritmusnak, hogy konnyen lehet belole
olyat is kihozni (programmodositassal persze), hogy elviseljen
nehany (mondjuk egy) kulonbseget, vagy delete-et, vagy insert-et!
Errol a 'Fuzzy' keresesrol (nem azonos a fuzzy logikaval) legkozelebb
irok majd, mert felek, hogy tullepem a sor limitet.
(Apropo, moderatorok, illetve Hix :) Jozsi: nem lehetne nagyobbra
venni a sor limitet? :)
István
-- Istvan Marosi -- http://www.sch.bme.hu/~marosi --
-- Recosoft Ltd. -- mailto: --
|
On 18 May 98 at 5:42, Antal Kovacs  > wrote:
> A problema: Nem ismerem a keresendo bitsorozatot!!!
> Tehat a legtobb ismetlodo bitsorozat kell megtalalnia es
> le kell fedje az teljes (bit)intervallumot.
[ Mit ertesz ezen, hogy lefedni a teljes intervallumot?]
Lehet, hogy a Lemper-Ziv-Welch (LZW) algoritmusbol kellene
kiindulnod, bar szabadalmaztatva van, ugyhogy csak penzert
hasznalhato. Nem pont ezt csinalja (eredendoen tomoritesre talaltak
ki, a pkzip is hasznalja/hasznalta), tehat nem garantalja, hogy az
osszes ismetlodo sorozatot megtalalja, de nagyon egyszeru algoritmus,
idoben linearis a string hosszaval, es egyszeru kodolni is.
Statisztikailag elegendoen hosszu string eseten nagy valoszinuseggel
a legtobbszor elofordulo leghosszabb stringet lehet vele megtalalni.
Ha tobbszor vegigfuttatod, akkor viszont egyre pontosabban konvergal
a keresett dologhoz. Lehet, hogy ketszer futtava is mar eleg jo
eredmenyt ad, kerdes, hogy mire kell.
Leirnam, hogy hogyan mukodik, de akkor a masik cikkel egyutt mar tuti
tullepem a mai sorlimitet :(
István
-- Istvan Marosi -- http://www.sch.bme.hu/~marosi --
-- Recosoft Ltd. -- mailto: --
|
Ave!
A kovi rutin egy readln lenne, csakhogy nem ertem :(
mov dx,offset ide
mov cx,8 <- max ennyi karakterk olvas be
xor bx,bx <- billentyuzetrol olvas
mov ah,3fh
int 21h
A hiba: ha bekeresnel tobb, mint 8 karakter irok be,
akkor a kovetkezo meghivasnal egybol kilep s visszaadja
az elozoleg beirt felesleget. Tehat ay elso hivasnal beirom:
HAJRA LOKI
ekkor a visszadott ertek: 8 byte = "HAJRA LO"
ezutan megint meghivom, nem var semmire,
hibat nem jelezve kilep, s visszadja:
4 byte = "KI"#13#10
Nem ertem!!!! Segitseg!!!!
Bye,
Tooth 'Gabry' Gaabor
mailto:
post:H-4001 Debrecen P.O. Box 515, HUNGARY
--
OFFLINE CHAT with ELIZA (sponsored by Gabry :)
ELIZA: HI, I AM ELIZA TELL ME YOUR PROBLEM
YOU: .(roviden) valaszolj angolul es kuld vissza.
|
