"Nagyon rossz" hash függvény

Fejlesztés

Sziasztok!

Van egy apróhirdetési oldalam, ahol ki szeretném szűrni a többszörösen feladott hirdetéseket. Ehhez kellene egy olyan hash fv, ami a kismértékben eltérő szövegeket ugyanarra az értékre képezi le. Lehet, hogy az ilyet máshogy hívják, akkor elnézést, max javítom a címet :)

A forrás szöveg kb. 1000-2000 karakter.

A célplatform php, ha ott van már valami kész megoldás az nagyon jó lenne, de ha nincs az se nagy baj.

Köszi a segítséget!
pentike

  • 2390 megtekintés

( lguru | 2009. 04. 04., szo – 20:58 )

Ha szavanként haladva mehet, akkor ötletnek similar_text() ill. levenshtein() függvényeket nézd meg. Persze erre még ki kell találni egy jó bejárási algoritmust, ill. megoldani ideiglenesen a hasonlósági értékek tárolását, súlyozás alapján kiszórni stb.

Ezek metrikák. Ezek két elemet tudnak összehasonlítnani, megadva valamilyen értelemben vett távolságukat.

Az eredeti kérdés szerintem normát keres, ami minden egyes elemhez egy-egy számértéket rendel, és nem páronként hasonlít össze.

--
The Net is indeed vast and infinite...
http://gablog.eu

gondolj bele ha lehetne 1 db 1 dimenziós normád (azaz hash-t szeretnél) az egész emberi nyelvet ráültetnéd egyetlen számegyenesre? nem fog menni mert most nem darabokat (->hash ), hanem tartalmakat akarsz hash-elni, azaz daraboknál ha "a"- nak és "b"-nek ugyanaz a hashe és "b" és "c"-nek is, akkor "a" és "c"-nek is, viszon tamit te szeretnél ott nincs tranzitivtás, (pl egy betűcsere megengedett, de kettő már nem)

Nem is valódi metrika ez, pl. már az alaphalmaz sem lineáris. Attól még léteznie kellene ilyesminek: a klasszikus hash függvények is ráültetik bármely jólrendezett halmaz véges részsorozatát, nemhogy a számegyenesre, de egy véges halmazra.

Nem az az elvárás, hogy tökéletesen működjön, a véges értékkészlet miatt elkerülhetetlen a kulcsütközés. Elég ha "nagy valószínűséggel" működik.

--
The Net is indeed vast and infinite...
http://gablog.eu

Nekem elég, ha a balfékek 80%-át kiszűri, a maradékot letörlöm kézzel :)

Most éppen azon gondolkozom, hogy ha kiszórom a whitespace-eket, akkor a hossza +- kb. 3 lehet egész jó közelítés lenne, mivel így a szófelcserélés kiszűrve, tördelések kiszűrve, ha meg teljesen átfogalmazza, akkor már nem ugyanaz.

tehát jól értem hogy 1 jellemzőt szúrsz ki: integer(összbetűszám/7), azaz tehát nem kell pontosan uganolyan hosszúnak lennie? szerintem jó ez, de ahogy lentebb írtam ezt egy kicsit érdemesebb tágabbra venni, tehát lehet akár 10-20 betűszámeltérés, de több ilyen jellemzőt pl integer(átlagszóhossz*100) , összesen 3-5 ilyen viszonylag tág és ha többségük egyezik akkor lesz jó, persze nem betűszámlálás csak egyiknek kellene lennie és szerintem az átlagszóhossz jobb mert inkább ír oda +-2 szót mint minden szóhoz +-2 betűt, ami az átlagszóhosszt kevésbé véltoztatja,

tehát olyasmire gondoltam hogy
select id1, id2 where
(id1.szohossz==id2.szohossz && id1.stilisztika==.. ) ||
(id1.szohossz==... && id1.betűszám==..) ||
(id1.stilistika==... && id1.betűszám)

ahol a szóhossz és a betűszám kerekítve az emlytett módon, a stilisztika meg ... :)

lentebbi szúrkálódásomat ez alapján is írtam:)

úgy érzem a hogy elsiklasz a probléma felett azzal hogy úgyse kell pontosan, csak nagy valsz-el, így az sem fontos hogy egész más problémát oldasz meg: tehát milyen hasht ültetsz a,b,c-re ha a-b hasonló, b-c hasonló, a-c pedig nem?

( sibidiba | 2009. 04. 04., szo – 20:59 )

subscribe,

Ilyet már én is kerestem, és nem találtam, pedig biztos létezik. Olyan hash-szerű függvény, ami kicsit különböző bemenetekre kicsit különböző kimeneteket ad. (Míg a klasszikus hash függvények kicsit különböző bemenetekre minél különbözőbb kimenetet kell hogy adjanak.)

--
The Net is indeed vast and infinite...
http://gablog.eu

google suggestion, az pl. lehetne egy hash tábla egy ilyen "rossz" hasz függvénnyel: ha nagyon kevés találati eredmény van, mivel valószínű az elgépelés, a hash táblában a sok találatos szomszédjait ajánlhatja.

--
The Net is indeed vast and infinite...
http://gablog.eu

Bocsi, de rosszul érzed :P Szerintem olvasd el még1x mit írtam. Minden hasht tekinthetünk normának, mert az alaphalmazbeli elemekhez számokat rendel. Nem topológiai értelemben vett norma azonban, mert pl. az alaphalmaz nem lineáris tér.

Alapvetően nem a gugliról beszéltem, hanem a "google suggestion"-ról. Ha félregépelsz google-ben egy szót, akkor a google gyakran felajánlja a helyes formát keresésre, pl.
Nem azt állítom, hogy így van megcsinálva, de lehetne így: az összes kulcsszót tárolják egy hash táblában. A tábla hash függvénye olyan, mint amit éppen keresünk. Ha egy keresés kevés találatot ad, de a hash táblában a szomszédai (azaz a hasonló kulcsszavak) közül az egyik kimagaslóan sokat, akkor azt felajánlja.

--
The Net is indeed vast and infinite...
http://gablog.eu

a fentebbi hash függvényednél sikerült félrevezető példát kitalálnom, meaculpa,

ott nincs igazad, hogy akkor a gugli elgépelések alapján minden begépelhető karaktersorozat sorba állítható, és ha épp annál a keresésnél kevés van, balra meg jobbra megyünk, amíg elég sok találatot találunk, de nem ilyen egyszerű a helyzet se a keresésnél, se a jelen példánál mondjuk az összkarakterszámmal nem írható le, csak elvileg működőképessé tehető és szerintem itt tévedtél el, mert a gyakorlatban egyszerűen a nyelv nem írható le ilyen egyszerűen,

én pedig ott találtam túl egyszerű példát hogy az "lineáris" és valóban ami távolra került a hash kódoddal, az tényleg nem hasonló; de akkor legyen hasonló a legfeljebb 1 karakter eltérés: aaa aab ... bbb, ezeket hogy rendezed sorba? nem gondoltam végig, ha ezt is sikerült elrontanom, majd kitalálok egy bonyolultabbat, de talán már érthető mire gondolok, egy sokdimenziós térben az összes pont adatát, tehát páronként milyen messze vannak egymástól, akarod 1 dimenzióba zsúfolni..

ha jól sejtem ehhez van elég tudásod vagy utánanézni és megérteni vagy nekem elmagyarázni hol tévedek :)

persze az aaa .. bbb példára mondhatod hogy nem kell tökéletesen és már néhány hibát megengedsz, de ez még csak 2 dimenzió, most (és máskor se:) nem tudom levezetni hogy mennyire nőnének ezek a hibák úgy gondolom hogy beérem egy ellenpéldával!:) , egész biztos kezelhetetlen mértékben nő a bonyolultság->hibák, ha a karakterszámot és a betűk számát növelem máris nőttek dimenziók, a természetes nyelvet pedig nem próbálom meg számolni :)

1. Ezt honnan vetted: "minden begépelhető karaktersorozat"? A hash táblában a valaha összes keresett önálló kifejezés lenne. Ez nem "olyan" nagy. Ez amúgy is megvan nekik (ld. google trends). Csak egy olyan hash táblában kell őket tárolni, aminek a hash függvénye olyan, mint amit keresünk. Egy hash tábla *nagyon* egyszerűen iterálható...

2. "mert a gyakorlatban egyszerűen a nyelv nem írható le ilyen egyszerűen" Te miről beszélsz? :D Nem vagyok nyelvész, de abban biztos vagyunk, hogy itt csakis korlátos hosszú karaktersorozatokról beszélünk egy korlátos ABC-ből.

3. 'a'->0, 'b'->1 ; aaa aab ... bbb -> 000 001 ... 111

4. Akárhány példa sorozatot mondasz, mindegyikre fogok tudni mondani jó hozzárendelést. Elemenként nagyon könnyű bővíteni ezt a halmazt, mivel nem várunk el tranzitivitást. A feltétel egy valószínűségi szórásra vonatkozik. Mindig el tudod helyezni úgy a következő elemet, hogy a feltétel továbbra is teljesüljön. Mivel a lehetséges alaphalmazok száma megszámlálható, itt már teljes indukcióval igazoltuk a függvény létezését. No de melyik ez a függvény?

5. Szerintem nézz utána a hash függvényeknek. Létezik belőlük elég sok fajta. A legtöbb arra törekszik, hogy kicsit különböző bemenetre (nagy valószínűséggel) nagyon *különböző* kimenetet adjon. Minden ABC-beli sorozatból egy korlátos egész szám lesz. [ABC]^n -> {0,1}^k (n,k e N) Pontosan ugyanilyen leképezésre van szükségünk, csak pont hogy kicsit különböző bemenetre (nagy valószínűséggel) nagyon *közeli* kimenetet adjon.

--
The Net is indeed vast and infinite...
http://gablog.eu

nem értem a hozzárendelésed: abb-bbb hasonló, baa-bbb nem hasonló pedig 011-111 és 100-111 különbség pont fordítva mondaná (határt beállítva legalább az egyikre mást)

(még nem vagyok benne biztos hogy igazam van, de ha igen, az hogy egy nyelvet hogy lehet leírni nem karakterenkénti átírásról van most szó, hogy a legegyszerűbb számelméleti tételekkel játszunk, hanem pl az adott szöveg most milyen hosszú szavakat tartalmaz, milyen a hangulata, stb.. amikor te értelmezed, nagyon sok dimenzióban látod, és abban tudod elhelyezni és meg tudod mondani hogy 2 elég közel van-e egymáshoz, egy ilyen fvt szeretnél, tehát _van_ egy nagyon sok dimenzióban nem túl bonyolult leírása a fv-nek, és ezt akarod 1-be belezsúfolni..)

btw nem vagy normális hogy ilyenkor billentyűt püfölsz ;)

( hory v | 2009. 04. 04., szo – 21:27 )

Egyszeru. Fogod a szoveget, szavakra bontod, es egy hashbe betomod az osszeset, majd az egymast koveto szavakat is, mondjuk 4-5 szoig.

Az osszehasonlitas ugy megy, hogy az egyik hashbol kivonod a masikat, igy megkapod azokat a szavakat + szokapcsolatokat, amelyek csak az egyik szovegben vannak benne.

Ezutan nemi kiserletezgetes kovetkezik, hogy mekkora pontszamtol szamitod ugyanannak a ket hirdetest.

Ez persze primitiv, de a szinten primitiv egyedek ellen jo megoldas. Es lekodolni se nagy szam. :)

Ez pont azért nem működik, mert hagyományos a hash. Így kicsit különböző szavak nagyon különböző helyen lesznek. Pont olyan hash tenne eleget a kritériumnak ami a kicsit különböző szavakat egy hash táblában egymáshoz közel helyezne el.

--
The Net is indeed vast and infinite...
http://gablog.eu

Ezzel az a baj, hogy nem tudom előre kiszámolni az egyes hirdetésekre és ez nagyszámú hirdetésnél meglehetősen erőforrásigényesnek tűnik. Olyan megoldás kellene, amit egy hirdetés feladásakor ki lehet számolni az adott hirdetésre és utána már csak egy SELECT kell, hogy egyezik-e a többivel vagy sem.

Tehát a hirdetésből egy szám lesz (norma) amihez ha elég közel van egy másik, akkor a kettőt azonosnak tekintjük.

Mar hogyne tudnad. A hash-t le lehet tarolni utana, pl. serialize, es bedobni egy mysql tablaba, blobkent.

Amugy igen, eroforrasigenyes. De ezt a fentebb leirt hash-t felejtsd el. Ilyen nincs. Hogy miert? Mert a szokvanyos hash-ek egy nagy szoveget kepeznek le 16 bytera. Ebbe belefer az, hogy ha 1-2 karakter kulonbozik, akkor mas legyen az erteke, de az mar nem, hogy felismerje pl. azt, hogy a mondatok mar sorrendben vannak. Es akkor ez meg csak a legprimitivebb hirdetes-ismetlodes volt.

Tehat ha talalsz is valamilyen kesz algoritmust erre (szinte biztosan van BTW - google), akkor se 16 byte-os hash-t fogsz kapni, hanem kilobyte-os nagysagrendut, es az osszehasonlitas is igencsak eroforrasigenyes lesz, nem sima <, > vagy =.

( tomaza | 2009. 04. 04., szo – 21:45 )

szerintem elvileg (( ->azaz nem részletezném,)) nem fog menni 1 darab hash, csak úgy hogy jellemzőket szedsz ki a szövegből, majd pedig ahány jellemzőt kiszedsz annyiszor kell végigmenni (az 1 hashez-képest), és ha elég sok egyezik akkor lesz jó
(pl egy jellemző: átlagszóhossz, az állítgatás pedig hogy mennyire kerekíted; vagy egymás utáni szavak hosszának összefüggése...)