Nagy István
A cikk elöljáróban megvizsgálja a hasonlóság és a szöveghasonlítás területeit. Ez utóbbi kapcsán bevezeti az asszociatív szövegkeresés fogalmát, majd olyan, az asszociatív szövegkeresésre épülő fejlesztési irányokat vázol fel, melyek a mainál hatékonyabb, "emberszerűbb" számítástechnikai rendszerek létrehozását teszik lehetővé.
A fejlesztési irányok közül legrészletesebben a pontatlanul ismert, vagy tárolt szöveges információ dokumentumban, illetve adatbázisban való keresését tárgyalja, majd a beszédidentifikációval és a zajos közegben történő szövegátvitellel foglalkozik. A technikai alkalmazások közül kitér az elektronikus szótárgépre, valamint az adatbáziskártyára. Különleges alkalmazásként említi meg a morfológiai és tartalom elemzések, valamint a különböző tudományos kutatások területeit.
A cikk végül bevezeti a mesterséges asszociáció fogalmát is, mint a mesterséges intelligencia azon ágát, mely a hibásan, vagy hiányosan ismert, vagy tárolt információ keresésének, azonosításának diszciplinája.
Kulcsszavak:
Asszociatív szövegkeresés, mesterséges asszociáció, hasonlóságelmélet, szöveghasonlítás, szövegkeresés, szövegfelismerés, beszédfeldolgozás, hibajavító szövegátvitel, asszociatív szótár, adatbázis gyorsító kártya, morfológiai elemzés, tartalomelemzés.
Előszó
Ha egy szakterületen elterjed egy új módszer, egy új technológia, akkor az általában kihat az egész szakterület fejlődésére. A számítástechnika ma még a "pontos" információk kezelésének szakterülete a "mesterséges intelligencia" címszó alatt 1980-ban megfogalmazott vágyálmok ellenére. Azt, hogy az akkori célok kis része valósult meg eddig, csak részben magyarázza a technikai eszközök nem kielégítő fejlettsége (számolási sebesség, tárolási kapacitás, hardver-szoftver architektúra, stb.), a valódi ok talán inkább az uralkodó szemléletben található. Szövegek összehasonlítására ugyanis már 1980-ban közöltek eljárást [2.4], és e cikk szerzője 1982-ben fejlesztett ki egy hatékony algoritmust az asszociatív szövegkeresésre, mely mint látni fogjuk igen sok alkalmazásban az újszerű működés motorja lehet. Mégis ma, 1999-ben még mindig nem képesek a legnagyobb és legelterjedtebb programrendszerek (szövegszerkesztők, adatbázis- és táblázatkezelők, stb.) sem biztosítani az akár egyetlen karakterrel elrontott szöveges adat megtalálását. A cikkbeli alkalmazási példák, javasolt fejlesztési területek nyilván még bővíthetők, de talán ezek is meggyőzően mutatják az asszociatív szövegkeresés sokoldalú alkalmazhatóságát.
0. Bevezetés
A legkorszerűbb adatbáziskezelő rendszerek hatalmas mennyiségű adat tárolását, és a legkülönbözőbb szempontok szerint való javítását, kiegészítését valamint lekérdezését teszik lehetővé. Működésük feltétele azonban a pontos adatmegadás. Adatbevitelkor, vagy lekérdezéskor egyetlen karakter kihagyása, vagy melléütése is információvesztéshez vezethet.
Tekintsünk például egy dokumentáció nyilvántartó rendszert, és tegyük fel, hogy keressük azon dokumentumokat, melyek az ortopédia témakörével foglalkoznak. Ha megfelelő dokumentumkörben folytatjuk a keresést, akkor az "ortopédia" szó keresésével viszonylag hamar többet is találunk. A mai nyilvántartó és adatlekérdező rendszerek általában lehetővé teszik az alstring szerinti keresést. Így az "ortopéd" szótő segítségével való keresés nyomán azokat a dokumentumokat is megtaláljuk, ahol csak az "ortopédiában", "ortopédus", "ortopédiája" szavak szerepelnek. Természetesen egy-egy újabb keresési eljárás során megtalálhatjuk az "orthopaed", az "orthopćd", valamint az "orthopäd" tövű alakokat tartalmazó angol, latin és német nyelvű dokumentumokat is. Amennyiben bennünket a francia, holland, vagy spanyol nyelvű dokumentumok is érdekelnek, megfelelő szótárakkal és természetesen újabb és újabb keresésekkel elérhetjük ezeket is. Feltéve, hogy...! Aki az "orthopéd", "orthoped", vagy az "ortoped" tövű szavakat begépelte talán csak régen forgatta a Helyesírási Tanácsadó Szótárt, az "artoped", az "otopéd", valamint az "ortoppéd" tövű szavak beírója pedig egyszerűen csak fáradt volt már. Ettől azonban az illető dokumentumok még fölöttébb érdekesek lehetnek számunkra. Próbálkozhatunk persze más kulcsszavak alapján való (újabb és újabb) keresésekkel (nehéz eset), valamint a teljes dokumentum gyüjtemény átnézésével (teljesen reménytelen). A nagyon nagy rendszereknél azt szokták mondani, hogy a hibásan tárolt adat elveszett. Persze ezt nehéz tudomásul venni...
1. A hasonlóságelmélet alapjai
1.1. A hasonlóság általános tulajdonságai
A hasonlóság fogalmát sokmindenre használjuk, azonban a különböző típusú objektumokra más és másfajta módon értelmezzük. Másként hasonló két háromszög, két épület, két ember, vagy két történet. Mi elsősorban az úgynevezett véges szimbólumkészlet fölötti véges láncok hasonlításával fogunk foglalkozni, de hogy közelebb kerüljünk a gyakorlati alkalmazásokhoz, inkább egyszerűen csak a valamilyen ábécé fölötti karaktersorozatok, a szövegek hasonlításáról beszélünk.
Az alábbiakban a hasonlóság általános tulajdonságaival fogunk foglalkozni olyan esetekben, amikor a vizsgált objektumok halmaza véges.
A hasonlóságot bár sokszor használjuk az egyenlőség (vagy legalábbis bizonyos tulajdonságokban való egyezőség) értelmében, a különbségek mégis igen fontosak. Ha egy nyilvántartó rendszerben azokat az objektumokat keressük, melyeknek valamely tulajdonságuk megegyezik egy előre megadottal, akkor a keresés egyértelmű feladat, és az így kiválasztott objektumok e feladat helyes megoldásai. Más a helyzet azonban akkor, ha az előre megadott, úgynevezett kulcs objektummal nem megegyező, csak ahhoz "elegendően" hasonló tulajdonságú objektumokat keressük. Már a feladatkijelölésből is "látszik", hogy a hasonlóság egy metrikus teret generál, amelyben a kulcs van az origóban, és az ehhez hasonlóbb objektumok közelebb, a kevésbé hasonlók pedig távolabb helyezkednek el.
Ez a tér véges, hiszen az objektumok halmazának végességét kikötöttük. (Egy nyilvántartó rendszerre ez triviálisan teljesül.) Nevezzük ezt a teret véges hasonlósági térnek, és az egyszerűség kedvéért adjuk meg a hasonlóságot százalékban. Ekkor 100% jelenti a teljes hasonlóságot, vagyis az egyezést (egyenlőséget), és e térben legyen a távolság a hasonlóság komplemense, vagyis a (100-hasonlóság) érték. Ez annyit jelent, hogy a véges hasonlósági térben a maximális távolság 100, ami - tekintettel arra, hogy a tér a végessége folytán korlátos is - tetszőleges távolságfogalom használata mellett is normalizálással mindig elérhető. A gyakorlatban azonban nem a távolságra, hanem közvetlenül a hasonlóságra határozunk meg valamilyen függvényt, és a szokásos hasonlóságdefiníciókra könnyen belátható, hogy a véges hasonlósági tér valóban metrikus. Adott objektumhalmazon és adott hasonlóságdefiníció esetén a fenti tér már felépíthető. Ebben a hasonlósági térben a vizsgálat szempontjából az origó a kulcs objektum.
Ha az "elegendő" hasonlóságot határhasonlóságnak nevezzük, akkor a kulcshoz való hasonlóságuk szerint kiválasztott objektumok e térben a kulcs körüli 100-határhasonlóság sugarú "gömbön" belül lesznek. Azonban a megoldás egyáltalán nem egyértelmű (a hasonlóság különböző lehetséges értelmezése miatt), és az is előfordulhat, hogy a "leghasonlóbb" egyáltalán nem is megfelelő. A hasonlósági rendszerek ezért általában interaktívak, azaz lehetőséget adnak a felhasználónak, hogy kiválassza a megfelelő objektumokat. Vannak azonban esetek, amikor dönteni kell (például egy robot szóbeli vezérlésénél, egy dokumentum kiválasztásánál, stb.). Még ilyenkor is a legtöbbször megtehető egy visszakérdezés, de az mindenképpen biztos, hogy felelős döntés csak akkor hozható, ha a lehetséges objektumok "elég távol" vannak egymástól a fentiekben értelmezett metrikus térben.
A hasonlósági térrel kapcsolatban megemlíthető néhány további jellegzetesség. Az egyik mindjárt az, hogy az egyenlőség nem generál metrikus teret. Egy objektum vagy egyenlő egy másikkal, vagy nem. Hasonlóság esetén azonban sosem az a kérdés, hogy fennáll-e a hasonlóság (ennek így nincs is sok értelme), hanem, hogy milyen mértékű az. A másik érdekesség a fenti hasonlósági tér szerkezete. Bár általában igaz az, hogy bármely metrikus térben lehet a tér objektumai között valamiféle hasonlóságot értelmezni például a távolság valamilyen komplemense, vagy az inverze segítségével, azonban a jellegzetes hasonlítási problémák nem ilyen terekben merülnek fel. Ennek az az oka, hogy egy minta objektumhalmaz elemeit általában olyan kulcs objektummal kell hasonlítani, mely nem is eleme ennek a minta halmaznak (éppen ezért van szükség a hasonlóság vizsgálatra, különben elég lenne az egyenlőséget vizsgálni). Ennek értelmében minden új kulcs esetén ki kell bővíteni a mintákból álló hasonlósági teret. A tér szerkezete tehát állandóan változik. A vizsgálat szempontjából a kulcs az origó, és a mintahalmaz minden eleme általában nullánál nagyobb távolságban helyezkedik el ettől. A hasonlóságvizsgálat során fel sem építjük az egész teret, hiszen az egyes mintaelemek egymástól való távolsága általában nem is érdekel minket.
Tovább vizsgálva az egyenlőség és a hasonlóság közötti eltérést megállapítható, hogy míg az A=B és B=C állításokból következik az A=C állítás (ezt nevezik tranzitivitásnak), addig a hasonlóságra ez általában nem teljesül, azaz A~B és B~C esetén általában nem igaz, hogy A~C. (Ez könnyen belátható, ha az evolúcióra gondolunk, vagy a Hold látszólagos alakváltozásaira.) Végülis megállapíthatjuk, hogy míg az egyenlőségre a fenti tranzitivitáson kívül fennáll a reflexivitás (azaz minden objektum egyenlő önmagával), és a szimmetria (vagyis az A=B állításból következik B=A), addig a hasonlóságra csak ez utóbbi kettő teljesül (vagyis minden A és B objektum esetén A~A, és az A~B állításból következik B~A), tehát az egyenlőség egy speciális hasonlóságnak tekinthető.
Miután eléggé szétválasztottuk az egyenlőség és a hasonlóság fogalmát, érdemes megvizsgálni a struktúrált és a struktúrával nem rendelkező (struktúrálatlan) objektumok hasonlóságának viszonyát.
Először is struktúrálatlannak tekintünk egy objektumot a hasonlóság szempontjából, ha a hasonlításban résztvevő azonosítói (attribútumai, elemei) egy rendezetlen halmazt alkotnak. Tipikusan ilyen egy objektum tulajdonsághalmaza. Ekkor az egyes tulajdonságok sorrendje érdektelen. Például a {magas, szőke, férfi, felemás cipőben} tulajdonságleírás azonos (egyenlő) a {férfi, felemás cipőben, szőke, magas} tulajdonságleírással. A {szőke, alacsony, nő, felemás cipőben} tulajdonságú "objektum" az előbbi "objektumhoz" egy triviális mérték szerint 50%-ban hasonlít. (Nyilván az adatbázisok rekordjai ebben az értelemben struktúrálatlanok, hiszen az egyes adatmezők sorrendjének nincs jelentősége.)
A hasonlóság szempontjából struktúrált objektumok például az egyszerű vonalas arcrajzok, ahol a szem, a fül, az orr, stb. egymáshoz képest különböző elhelyezkedése, még az elemi formák egyezése esetén is egészen eltérő arckifejezést eredményez. Ahogy már jeleztük, mi a későbbiekben a véges szimbólumkészlet fölötti véges hosszúságú láncokkal fogunk foglalkozni. Ezeket lineáris struktúrájú véges objektumoknak, vagy rövidebben véges lineáris struktúráknak nevezzük. Ilyenek például a betükből felépülő szavak. Ha azt szeretnénk, hogy az általunk definiált hasonlóság ne legyen ellentmondásban a hétköznapi beszédben elterjedttel, akkor például a "window" ("ablak" jelentésű angol) szóhoz hasonlóbbnak kell értékelnünk a "widow", a "uindow", vagy akár a "wdnow" szavakat, mint például a "wodniw" szót, holott ez az eredeti szó minden karakterét (és csak azokat) tartalmazza (csak éppen fordított sorrendben), és így a struktúrálatlan objektumoknál jelzett hasonlósági mérték szerint ez lenne a leghasonlóbb.
Általában azt mondhatjuk, hogy a struktúrával rendelkező objektumok összehasonlításánál az objektumokat felépítő elemek egyezésén túl, azoknak a struktúrában elfoglalt helyét is figyelembe kell venni. Ez a szemlélet a hasonlóságelméletet lényegesen nehezebbé, de lényegesen hasznosabbá is teszi. (A matematikai statisztikában is egészen másként értelmezzük például az átlag fogalmát adathalmazok, mint idősorok esetén, és a spline fogalmát struktúrálatlan adathalmaz esetén például nem is tudjuk értelmezni.)
Egy megjegyzést még fűzünk vizsgálatunk tárgyának kijelölésében használt "véges szimbólumkészlet" kifejezésre vonatkozóan. Ha ugyanis a láncokat felépítő elemek halmaza végtelen, akkor általában nem lehet az összehasonlítandó láncok egyes elemeinek egyezéséről beszélni. Ilyenkor jellemzően véges számú osztályba soroljuk az elemeket (és így visszajutunk a véges szimbólumkészlethez). Ekkor azonban az egyes elemekkel való azonosságról sem lehet beszélni. (Tipikusan ilyen például a kézírás, vagy a beszédjelek azonosításának feladata.) Ez esetben az objektum azonosítása (véges halmazból való kiválasztása) előtt még el kell végezni az objektum egyes elemeinek azonosítását is. Nevezzük ez utóbbit elsőfajú azonosításnak (és az ehhez vezető hasonlítást elsőfajú hasonlításnak), és az (esetleg részben hibásan) azonosított elemekből álló objektum azonosítását másodfajú azonosításnak (mely a másodfajúnak nevezhető hasonlítás által érhető el). Ebben az esetben összefoglalva a korábbiakat azt mondhatjuk, hogy mi a továbbiakban véges lineáris struktúrák másodfajú hasonlításaival fogunk foglalkozni. (Egyébként az elsőfajú hasonlítás esetén a hasonlósági tér általában már nem véges, így az ezzel kapcsolatban korábban mondottak csak részben teljesülnek.) Megjegyezzük, hogy a számértékű elemekből, vagy kódokból álló láncok (az összetett számok, dátumok, koordináta értékek, numerikus adatsorozatok, gépkocsi rendszámok, stb.) nem tartoznak vizsgálódásunk tárgykörébe.
1.2. A szöveghasonlítás, az asszociatív szövegkeresés
A szöveghasonlítás célja: hiányosan, vagy hibásan ismert, vagy tárolt szöveges adatok megkeresése tetszőleges információs rendszerben, vagy szöveges dokumentumban. Az ilyen típusú szövegkeresést - utalva gondolkodásunk valamilyen hasonlóság alapján történő képzettársítási képességére - asszociatívnak nevezzük.
Általánosabb értelemben azt mondhatjuk, hogy az asszociatív szövegkeresés feladata véges szimbólumkészlet fölötti lineáris struktúrájú objektumhoz kiválasztani az ilyen objektumok véges teréből a hozzá megadott mértéknél hasonlóbb objektumokat. Az asszociatív szövegkeresés során tehát véges lineáris struktúrákon végzünk másodfajú hasonlítást, azaz "szöveghasonlítást".
A szöveghasonlítás lehetősége azon alapszik, hogy a szövegek véges karakterkészletből felépülő véges hosszúságú szekvenciák, melyek annál hasonlóbbaknak tekinthetők, minél nagyobbak a "közös gyökeik", és minél kevesebb változtatással "vihetők át" ezek egymásba. Ez az értelmezés összhangban van a szöveghasonlóság hétköznapi, "humanoid" felfogásához. Lényege, hogy két karaktersorozat hasonlóságát a közös karaktereket tartalmazó, azonos hosszúságú alsorozatok (a "közös gyökök") relatív rendezetlenségéből származtathatjuk. (Ennek pontos definiálása elég bonyolult, de az azonos karaktereket nem tartalmazó szövegnek a karaktercserékkel előállított módosulásával való relatív rendezetlenségét például egyszerűen lehet jellemezni a permutáció elméletből ismert inverzió fogalmával.) Nyilván a megegyező szövegek relatív rendezetlenségének mértéke nulla, a hasonlóságuk pedig maximális. A fentiekből érzékelhető, hogy a hasonlítás és a rendezés sok vonatkozásban rokon feladatok.
Az előző pontban a hasonlóság elméleti megközelítésének sokoldalúságáról szóltunk, nem könnyű azonban a legegyszerűbb struktúrált objektumok, a láncok hasonlításának gyakorlati megvalósítása sem. Ha mindkét összehasonlítandó szövegből elhagyjuk a másikban nem szereplő karaktereket, akkor általában két különböző hosszúságú szöveg keletkezik. A triviális esetektől eltekintve ekkor egy speciális mintaillesztési feladatot kell megoldani, melynek eredményeként a "közös gyököket" kapjuk. Ez nemcsak rendkívül bonyolult algoritmuselméleti probléma, hanem igen időkritikus is, hiszen ettől függ a hasonlóságvizsgálat hatékonysága.
Látható tehát, hogy a szövegek hasonlóságának vizsgálata sok vonatkozásban különleges, esetenként körülményes módszereket igényel. Kétségtelen tény viszont az is, hogy új távlatokat nyit olyan, eddig intellektuálisnak tekintett területeken, mint például az asszociatív szövegkeresés, a beszédidentifikáció, vagy a zajban torzult szövegek javítása.
2. Alkalmazások
2.1. Szöveges információ asszociatív keresése
Az asszociatív szövegkeresés legfontosabb gyakorlati alkalmazása kétségkívül a nagyméretű szövegállományokban, illetve szöveges adatbázisokban való keresés.
Akár adatbevitelkor, akár lekérdezéskor torzul a szöveg, az egyezésen alapuló keresés eredménytelen lehet, amint a korábbi példák során erre már kitértünk. A feladat gyakorlati megvalósításában nyilván nagy segítséget jelenthet egy platform-független szabványos lekérdező nyelv, például az SQL valamilyen kiterjesztése. A kiemelten fontos, gyakran használt, nagyméretű dokumentumokat (például kézikönyveket, szervízkönyveket, stb.) célszerű asszociatív keresést is biztosító, úgynevezett intelligens hypertext rendszerekbe építeni. A szakértői rendszerek szintén alkalmazhatják ezt a lehetőséget, sőt új típusú képességként még bővítheti is eszközkészletüket. Az asszociatív szövegkeresés természetesen nemcsak a nagy nyilvántartó és dokumentációs rendszerek számára hasznos. Jó segítséget nyújthat egy szövegszerkesztő, vagy táblázatkezelő programban is. Célszerű lehet ezért mindjárt az operációs rendszer részeként megvalósítani. Az asszociatív keresés gyakorlati alkalmazásaként megemlíthetők még a konferencia regisztrációs és a személyazonosító (beléptető) rendszerek is.
2.2. Adatbáziskezelés
Bár az előző pontban már utaltunk az adatbázisokra, tekintettel a terület fontosságára érdemes alaposabban is megvizsgálni, hogy miként fog hatni az adatbáziskezelés gyakorlatára az asszociatív szövegkeresés.
Feltételezésünk szerint az asszociatív szövegkezelést alkalmazó rendszerekben más lesz az adatbázisok szerkezete; több lesz a szöveges (mégpedig elsősorban szabadszöveges) adatmező. Ennek következtében ugyan nagyobbak lesznek az adatbázisok, és a keresési idő viszonylag szintén megnő, de a várható előnyök és a technikai eszközök gyors fejlődése ezt rövid idő alatt feledtetni fogja.
Vizsgáljuk meg milyen előnyöket rejt egy jelentős mértékben szabadszöveges adatmezőkkel rendelkező adatbázis, melyben asszociatív szövegkeresést használunk. (Természetesen ez nem jelenti azt, hogy ebben nem lesznek egyéb típusú adatmezők.)
1./ Adatbiztonság
Talán meglepőnek tűnik, hogy éppen a legsérülékenyebbnek tekintett szöveges adat eredményez adatbiztonságot, ám könnyen belátható ennek igazsága. Egy kódolt adat (például egy adószám) bármely elemének megváltozása általában az adat javíthatatlan torzulásához vezet. Egy szöveges adat "érthetőségét", vagyis asszociatív kereséssel való megtalálhatóságát a benne lévő redundancia sokszor még a nagyobb alaki torzulással szemben is megőrzi.
2./ Sebesség
Bár egy asszociatív keresés nyilván lassúbb egy szövegegyezéses keresésnél (és főként egy numerikus reláció szerinti keresésnél), azonban ha több próbálkozásra van szükség (lásd például a Bevezetésben említett példákat), akkor az egy keresésre jutó idő akár nagyságrendekkel kevesebb is lehet, nem beszélve arról, hogy bizonyos esetekben csak ez eredményes.
3./ Egyszerűbb és rugalmasabb adatszerkezet
A hagyományos adatszerkezet tervezése során a szöveges adat elkerülése érdekében sokszor szétválasztják az összetartozó adatokat.
Tekintsünk például egy orvosi rendszert, mely az allergia vizsgálatok eredményeit tartalmazza. A "parlagfű", "toll", "kutyaszőr", stb. allergének neveiből jellemzően külön adatmezőket csinálnak, ahelyett, hogy a "nincs", "gyenge", "erős" reakciókategóriák által jelölt adatmezőkben sorolnák fel a vonatkozó allergéneket. Ekkor például az ERŐS_REAKCIÓ adatmezőbe beírt "parlagfű, házipor, semicillin" szöveg nemcsak egyszerűbb adatstruktúrát eredményez, hanem az asszociatív keresés révén jelentős mértékben véd a beírási hibáktól. (Nyilván e mezőben a lekérdezés számára javíthatóan torzult adat a "Szemicilin", míg a lekérdezésben már nem javítható a torzulás, ha egy SEMICILLIN nevű mezőben a "++" hatáserősség megjelölés helyett "+++" áll.)
A kisebb számú adatmező az áttekinthetőbb adatszerkezeten és a könnyebb felhasználói használaton túl még a működést is gyorsítja (hiszen így az azonos jellegű adatmezők mindegyike helyett elegendő az összevont adatmezőt végigvizsgálni), és rugalmasabbá is teszi a rendszert (ugyanis új tulajdonságjegy esetén - az előbbi példánál maradva a "teveszőr" allergén megjelenésekor - nincs szükség új adatmező bevezetésére).
A fentieket úgy foglalhatjuk össze, hogy a szöveges adatbázisokban az eredményezi az egyszerűbb adatszerkezetet, hogy az objektum tulajdonságjegyei mezőnevek helyett mezőértékként szerepelhetnek.
2.3. BeszédidentifikációR>
A beszédidentifikációnak van egy elterjedt és jól bevált módszere; az úgynevezett "teljes szavas" felismerés. A lényege, hogy a szókészlet minden eleméhez (szó alatt itt egy rövid kifejezés is érthető) tárolják a szó kimondásakor keletkező hangsor időtartományi grafikonját (valamilyen felbontással). A rendszer alkalmazásakor a felhasználó által kimondott szó hangsor-grafikonját statisztikai eszközökkel összehasonlítják a tárolt hangsor mintákkal. A módszer nyilvánvaló előnye, hogy a teljes-szavas hangminták viszonylag könnyen elkülöníthetők, mivel elég hosszúak. Ráadásul az ilyen rendszerek alkalmazásánál elvárható tagolt szóhasználat révén az egyes szavak elhatárolása sem okoz gondot. Az "elegendően hosszú" hangminták persze csak akkor különíthetőek el jól, ha "elegendően kevés" van belőlük. Mivel pedig egy új szó azonosításának megtanulásához nem használható fel a korábbi szavak azonosításának tapasztalata (hiszen minden szó egy különálló új minta), így az ilyen rendszer igen merev, és egyre nehezebben bővíthető.
Már régóta ismert, hogy a beszélt nyelvnek is van ábécéje, ez az úgynevezett fonémakészlet. Fonémából természetesen több van mint betüből, hiszen egy mássalhangzó sokszor egészen másként hangzik szó elején, mint végén, másként magánhangzók között, mint mássalhangzó torlódásban. Ráadásul nemcsak az egyes nyelveknek különböző a fonémakészletük, hanem egy nyelven belül jelentősen különbözhet az egyes tájszólásoké, sőt valamennyire személyenként is más és más. Persze egy országon belül azért általában eléggé hasonlóak a fonémakészletek, különben nem értenénk meg egymást. A lényeg, hogy mivel a beszélt nyelv szavai a fonémákból úgy épülnek fel, mint az írott szavak a betükből, így egy fonémaidentifikáción alapuló beszédfelismerő rendszer legnagyobb előnye a modularitásból következő bővíthetőség. Az ilyen elven működő rendszer nyilván sokkal rugalmasabb, és csak a fonémák hangmintáit kell tárolni. A két módszer tehát úgy viszonyul egymáshoz, mint a képírás a betüíráshoz. Hogy miért terjedt el mégis a "teljes szavas" módszer? Azért mert a fonémaidentifikációs módszert két súlyos probléma terheli. Az egyik abból következik, hogy a szavakat folyékonyan ejtjük. Ebből következően a teljes szó hangmintájának elemzésekor el kell különíteni az egyes fonémákat. Tehát egyidejűleg kell elvégezni az elhatárolást az azonosítással. Ez természetesen nem mindig sikerül. Részben ebből következik a másik probléma, mely szerint az azonosított fonémaszekvencia helyenként hibás. Ennek egyébként oka az is, hogy egyes fonémák nehezebben azonosíthatók.
A fonémaidentifikációs módszer során tehát egy fonémaszekvenciába képezzük le a kimondott szót. Tekintettel arra, hogy a fonémákat már le tudjuk írni betükkel (egy fonémát általában több betüvel), így a kimondott szó írásképét kell azonosítanunk a fonémaszekvencia írásképével. Igaz, hogy még a minden elemében tökéletesen azonosított fonémaszekvencia írásképe is általában eltér a kimondott szó helyesen leírt írásképétől (például a kiejtés sajátosságai miatt), azonban e feladat a szókészletben történő asszociatív szövegkereséssel már megoldható.
2.4. Hibajavító szövegátvitel
Egyes ipari, közlekedési, katonai rendszerek hatékony, mégis memorizálható vezérlése/vezénylése (control/command), de a robotok szóbeli vezérlése is igényli egy korlátozott szókészlet biztonságos továbbítását. E területen alapkövetelmény a pontos szövegazonosítás, noha az adatátviteli rendszerek zajosak lehetnek. Shannon második tétele megadja az elvi lehetőségét annak, hogy zajos csatornán korlátozhassuk a kimeneti hibavalószinűséget. Hibás átvitel azonban egy jól megépített szövegátviteli rendszeren is lehetséges. Hogyan lehet a torzult szöveget azonosítani? Ez az alapprobléma. Kiegészítő problémaként felvethető, hogy "engedélyezett mértékű" szövegtorzulás esetén hogyan lehet rövidebb kódot előállítani, és ilyen módon nagyobb adatátviteli sebességet biztosítani? Ez azonban már egy jól kezelhető információelméleti feladat. Az alapprobléma megoldásához nyilván a korábban már említett erősen korlátozott "szókészlet" szükséges, ahol a "szavak" a hasonlóságok metrikus terében "eléggé távol" vannak.
Megjegyezzük, hogy a fenti szövegjavító eljárás az optikai karakterfelismerés (OCR) területén is alkalmazható (a másodfajú azonosítás során).
2.5. Intelligens elektronikus szótár
Nincs igazán átütő sikerük a jelenlegi elektronikus szótáraknak. Még a nagykapacitású, asztali számítógépekre telepített szótárprogramok sem tudtak a mindennapi használatban meghonosodni, pedig a megnövekedett nemzetközi kommunikációs igény igencsak indokolná elterjedésüket. Az alapvető probléma az, hogy ha egy szónak nem ismerjük a jelentését, akkor általában a pontos írásmódját, szótári alakját sem tudjuk. (Ez persze csak az idegen nyelvről történő fordításnál van így, de hát ez a tipikus feladat, lévén, hogy az ellenkező irányú fordítást általában hivatásos fordítók végzik.) A könyv alakú (írott) szótár használatában is a "böngésző" keresés az eredményes. Ekkor a feltételezett írott alakhoz hasonló címszavak között keresgélünk. Az elektronikus szótárak akkor válnak idegenszerüvé, amikor elvárják, hogy pontosan adjuk meg a szóalakot. Ez teljesen érthető a szövegkeresés szokásos módszerei alapján, de nem elfogadható a felhasználás szempontjából. Az e területen tapasztalt rugalmasság általában kimerül a szókezdő alstring elfogadásában (de az természetesen legyen pontos!). Ez az "egzaktság" különösen zavaró az olyan helyzetekben, amikor nemigen van lehetőség a hosszadalmas próbálkozásokra, másfelől a legkevesebb támaszunk van a pontos írásképre vonatkozóan. A kis tetszetős formátumú, soknyelvű és általában igen jelentős kapacitású (15-30 ezer szócikkű) hordozható elektronikus szótárak teljesen hasznavehetetlenek például egy piaci vásárlás során, holott éppen erre készültek.
Könnyen belátható, hogy nagy sikerük lenne e hordozható elektronikus szótáraknak, ha kezelni tudnák a hozzávetőleges, a többé-kevésbé hallás szerinti, fonetikus beírásokat.
2.6. Adatbázis gyorsító kártya
Az adatbáziskezelés túlzás nélkül tekinthető a legfontosabb számítógépes alkalmazásnak. Pénzügyi, banki és ipari rendszerek, közigazgatási, államigazgatási apparátusok válnának működésképtelenné, ha megsemmisülnének a számítógépes nyilvántartások. A feladat jelentőségéhez képest elég csekély erőfeszítés történt annak érdekében, hogy a tipikus, nagy erőforrásigényű adatbáziskezelési tevékenységeket valamilyen hardver eszközzel felgyorsítsák. Pedig az indexezés-rendezés, keresés-kigyüjtés folyamatai nyilván gyorsabban lennének végrehajthatók, ha e feladatok megoldásában kiegészítő áramkörök is részt vennének. Különösen igaz ez az egyik leginkább erőforrás-igényes tevékenységre, a szöveghasonlításra. Egy célszerűen megvalósított adatbázis gyorsító kártya a főprocesszor mellett, de attól függetlenül (akár saját processzorral, és nagy memóriakapacitással) olyan módon vizsgálhatja végig a megfelelően előkészített adatbázisállományokat, hogy a főprocesszor részére már csak a megtalált objektumok kívánt adatmezőinek listáját adja át. Ugyanez az áramkör a nagyméretű dokumentumokban való keresést is segítheti. Az adatbázis gyorsító kártya tehát az asszociatív szövegkeresés olyan hardvertámogatása, mely a nagy adatbáziskezelési, dokumentumnyilvántartó rendszerek működési sebességét növeli.
3. Egyéb alkalmazások
3.1. Morfológiai elemzés
A számítógépes szövegszerkesztők elterjedésével egyre több nyelven készítenek helyesírásellenőrző programokat. E programok lényeges része a morfológiai elemzés, mely a szavak toldalékmentesítéséből, és a kapott szótő szótárban való azonosításából áll. A szöveghasonlítás ebben az azonosításban nyújthat segítséget.
3.2. Tartalomelemzés
A tartalomelemzés különösen hasznos lehet a könyvtári rendszereknél, a szakirodalom kutatásnál, az irodalmi műalkotások elemzésénél. A tartalom szerinti keresés egyrészt feltételezi, hogy a dokumentum teljes egészében, vagy hiteles kivonat formájában rendelkezésre áll. másrészt, hogy szintén rendelkezésre áll egy szinoníma szótár, melyből generáljuk a keresett kulcsszavak (elsődleges kulcsok) szinonímáit, a másodlagos kulcsokat. (Megjegyezzük, hogy a másodlagos kulcsok halmaza tartalmazza az elsődleges kulcsokat is.) A tartalomelemzés alapművelete természetesen a másodlagos kulcsok (esetleg valamilyen logikai kifejezés szerinti) keresése a vizsgált dokumentumban. A szöveghasonlítás művelete ezen túl a másodlagos kulcsok generálásánál is szerephez jut.
A tartalomelemzés speciális alkalmazásaként említhetjük meg az automatikus vizsgáztatást, ahol a helyesírásilag hibás válaszok is értékelhetővé válhatnak.
3.3. Tudományos kutatások
Az asszociatív szövegkeresés során szöveghasonlításokat hajtunk végre. Értelmezésünk szerint pedig a "szöveghasonlítás" tárgya lehet bármely véges szimbólumkészlet fölötti véges szimbólumszekvencia, azaz véges lineáris struktúra. Ez lehet titkosírás, népművészeti motívumokból felépülő sorminta, események, tevékenységek sorozata, gondolatsor, egy regénynek, vagy egy versnek a szerkezete, a népmesék motívumszekvenciái, vagy éppen a DNS-láncok génszekvenciái. Mivel gondolkodásunk alapvetően lineáris struktúrákkal dolgozik (hiszen mind a helyváltoztatás, mind az idő múlása lineáris struktúrákat eredményeznek), így az általunk létrehozott objektumok jelentős része is ilyen. A gyakorlati kutatás elsősorban osztályozási tevékenység. Ehhez a vizsgált objektum és az osztályok reprezentáns elemeinek összehasonlítására van szükség, az imént felsorolt objektumtípusokra pedig a "szöveghasonlítás" elvégezhető.
4. A mesterséges asszociáció
A "szöveghasonlítás" fenti példáiban nem pontosan definiált objektumokat választottunk ki adott "szöveghalmazból". Ezt a kiválasztási folyamatot - utalva a gondolkodás hasonló tevékenységére - asszociatív szövegkeresésnek neveztük. (Pontosabb megfogalmazás szerint az asszociatív szövegkeresés során véges lineáris struktúrák másodfajú hasonlítását végezzük.)
A hasonlósági vizsgálatoknak a szövegeknél bonyolultabb struktúrákra való kiterjesztésével el lehet jutni más típusú asszociatív keresésekhez is. (Például az optikai karakterfelismerés elsőfajú hasonlítása révén kétdimenziós grafikus alakzatokhoz keressük asszociatív módon egy ábécé betüit.) Általában azon eljárások, módszerek összességét, melyek hatására a hiányos, vagy torzult információ alapján tudunk objektumokat kiválasztani (esetleg azonosítani), mesterséges asszociációnak nevezzük.
A mesterséges asszociációt, mint szakterületet a mesterséges intelligencia és a hasonlóságelmélet irányából tudjuk megközelíteni. Jelentőségét az adja, hogy a korszerű számítástechnikai eszközök technikai lehetőségei már megvalósíthatóvá teszik az ember számára megfelelőbb kommunikációs felület kialakítását. A leírt szövegnek, a beszédnek, a rajznak és általában az emberi kommunikációnak nem az irredundáns pontosság a jellemzője. Az ilyen objektumok általában nagy redundanciával, de éppen ezért nagy hibatűréssel, zajtűréssel rendelkeznek az emberi megértés számára. Az elsőfajú azonosításukra már vannak elég jó hibaarányú módszerek. Az így kapott (a számítógép számára már befogadható) információ azonban általában még túl pontatlan ahhoz, hogy segítségükkel a hagyományos rendszerekben elvégezhető legyen az identifikáció. A struktúrált objektumok másodfajú hasonlítási módszerei ezért várhatóan nagy fejlődésnek fognak indulni. Jelenleg a legnagyobb probléma az emberi megitéléssel konzisztens, de mégis megfelelő hatékonyságú (exponenciálisnál kisebb bonyolultságú) hasonlító algoritmusok kis száma.
IRODALOM
1. Hasonlóságelmélet (Similarity theory)
[1.1] Srejder, JU. A.: Ravensztvo, szhodsztvo, porjadok. Izdatyelsztvo Nauka, Moszkva, 1971. (orosz nyelven)
2. Szöveg felismerés (Text recognition):
[2.1] Sweet, J. A.: Information retrieval system. Science, 1963. 141. p.245-250.
[2.2] Cooper, W. S.: Expected search length: A single measure of retrieval effectiveness based on weak ordering action of retrieval systems. Journal of the American Society for Information Science, 1968. 19. p.30-41.
[2.3] Robertson, S. E. - Teather, D.: A statistical analysis of retrieval test: a Bayesian approach. Journal of Documentation, 1974. 30. p.273-282.
[2.4] Hall, P. A. V. - Dowling G. R.: Approximate String Matching. Computing Surveys, Vol. 12, No. 4, December 1980. p.381-402.
[2.5] De Heer, T.: Fuzzy Text Retrieval. In: MEDINFO-83, van Bemmel-Ball-Wigertz, Editors. (c) IFIP-IMIAé North-Holland (1983). p.128-131.
[2.6] Van Rijsbergen, C. J.: Information Retrieval. Butterworthand Co., Inc., 1985.
[2.7] Baeza-Yates, R. - Gonnet, G. H.: A New Approach to Text Searching. Communication of the ACM, Vol. 35, No 10, October 1992. p.74-82.
[2.8] Wu, S. - Manber, U.: Fast Text Searching Allowing Errors. Communication of the ACM, Vol. 35, No 10, October 1992. p.83-91.
[2.9] Sinha, R. M. K. - Prasada, B. - Houle, G. F. - Sabourin, M.: Hybrid Contextual Text Recognition with String Matching. IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol.15, No.9, September 1993. p.915-925.
[2.10] Marzal, A. - Vidal, E.: Computation of Nomalized Edit Distance and Applications. IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol.15, No.9, September 1993. p.926-932.
3. Beszédidentifikáció (Speech recognition):
[3.1] Tarnoczy, T. - Vicsy, K.: Some Remarks on the Perception of voiceless Stopconsonants. Acustica, Vol.43. 1979. No.2. pp.167-173.
[3.2] Ney H.: A Comparative Study of Two Search Strategies for Connected Word Recognition: Dynamic Programming and Heuristic Search. IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol.14, No.5, May 1992. p.586-595.
4. Hibajavító szövegátvitel (Fault-tolerant text transmission):
[4.1] Shannon, C. E.: Communication in the Presence of Noise. Proc.of the IEEE.72. 1984. No.9. p.1195.
[4.2] Kretzmer, E. R.: Generalization of a Technique for Binary Data Communication. IEEE Trans.on Com.Tech., February 1966. COMM 14, No.1.