Szövegelemzés
Szövegelemzési fogalmak:
Használat során a magas tf-idf érték magas kifejezés gyakorisággal és alacsony dokumentum gyakorisággal jár együtt, tehát így kiszűrhetőek a gyakori kifejezések. Egy-egy kifejezés tf-idf értéke akkor nagyobb, mint 0, ha az idf logaritmus belsejében az érték nagyobb, mint 1.
Attól függően, hogy a nevezőhöz hozzáadunk-e 1-et, egy olyan kifejezésnek, amely minden dokumentumban szerepel, nulla vagy negatív lesz a tf-idf értéke.
Absztrakt adattípus : amely absztrakt adatok halmazát adja meg (definiálja), nem törődve a konkrét gépi megvalósítással.
Pl.: tömb, lista, verem, sor, halmaz, kupac, fa, gráf, hálózat, binomiális kupac
Algoritmus : meghatározott számítási eljárás, a számítási probléma megoldási eszköze
Karakterizáló paramétere
1.A kiinduló adatok lehetséges halmaza
2.A lehetséges eredmények halmaza
3.A lehetséges közbülső eredmények halmaza
4.A kezdési szabály
5.A közvetlen átalakítási szabályok
6.A befejezési szabály
7.Az eredmény kiolvasási szabály
Algoritmus hatékonysági jellemzője:
A egy algoritmust, x egy bemenő adatot, n=|x | a bemenő adat méretét,D a lehetséges bemenő adatok halmazát.
Legyen TA(x) az A algoritmus végrehajtásának időigénye, SA(x) az A algoritmus tárigénye az x bemenet esetén.
Az algoritmus időbonyolultsága és tárkapacitás bonyolultsága
Az olyan halmazt, amely az őt felhasználó algoritmus során változik (bővül, szűkül, módosul) dinamikus halmaznak nevezzük. A dinamikus halmazok elemei tartalmazhatnak:- kulcsmezőt, - mutatókat (pointereket), amelyek más elemekre mutatnak. (pl: a következő elemre)
A verem (stack) olyan dinamikus halmaz, amelyben előre meghatározott az az elem, melyet a TÖRÖL eljárással eltávolítunk. Ez az elem mindig a legutoljára a struktúrába elhelyezett elem lesz.
A láncolt lista (linked list) olyan dinamikus halmaz, melyben az objektumok, elemek lineáris sorrendben követik egymást. A lista minden eleme mutatót tartalmaz a következő elemre.
Azt a rendező eljárást, melynek végén az azonos értékű kulcsok sorrendje megegyezik az eredetivel. stabil eljárásnak nevezzük.
Shell rendezés módszere:
A buborékrendezésnél tapasztalt lassú helyrekerülést igyekszik felgyorsítani azáltal, hogy egymástól távol álló elemeket hasonlít és cserél fel. A távolságot fokozatosan csökkenti, míg az 1 nem lesz. Minden növekmény esetén beszúrásos rendezést végez az adott növekménynek megfelelő távolságra álló elemekre. Mire a növekmény 1 lesz, sok elem már majdnem a helyére kerül.
Négyzetes rendezés módszere:
Felosztjuk az a forrás tömböt √n számú √n elemet tartalmazó részre (alcsoportra). Mindegyikből kiemeljük a legkisebbet. (Ez lesz a főcsoport.) Kiválasztjuk a legkisebbek legkisebbikét (a legkisebbet a főcsoportból) és azt az eredmény tömbbe írjuk, a főcsoportból eltávolítjuk. Helyére abból az alcsoportból ahonnan ő jött újabb legkisebbiket emelünk be a főcsoportba. Az eljárást folytatjuk, míg az elemek el nem fogynak.
Számjegyes rendezés módszere:
Azonos hosszúságú szavak, stringek rendezésére használhatjuk. (Dátumok, számjegyekből álló számok, kártyák, stb.) Legyen d a szó hossza, k pedig az egy karakteren, mezőben előforduló jegyek, jelek lehetséges száma, n pedig az adatok száma.
Edényrendezés módszere:
Feltételezzük, hogy a bemenet a [0, 1) intervallumon egyenletes eloszlású számok sorozata. Felosztjuk a [0, 1) intervallumot n egyenlő részre (edények). A bemenetet szétosztjuk az edények között, minden edényben egy listát kezelve. Az azonos edénybe esőket beszúrásos módon rendezzük. A végén a listákat egybefűzzük az elsővel kezdve.
A szöveg elemzési módszerek között megkülönböztetünk:
- inkrementális- dekrementális módszereket.
Az inkrementális módszerek lényege, hogy egy új hivatkozást azonnal osztályhoz rendel, vagy új osztályt hoz belőle létre, ha az mindentől nagyon távol esik.
Az inkrementális hozzárendelés lépései:
• Azonosítás: - a hivatkozási helyek és szövegrészek kiemelése.
• Normalizálás: - a hivatkozó szövegek transzformációja (egységes alakra hozása és tisztítása) és részekre bontás.
• Távolságképzés: - az adott kiemelt hivatkozási hely és az osztályok reprezentánsai távolságának kiszámítás.
• Hozzárendelés: - a hivatkozási helyek (és ezzel a hozzászólás) osztályhoz rendelése (vagy új osztály létrehozása).
• Reprezentálás: - új osztály létrehozása vagy régi osztály bővítése esetén reprezentáns választása.
A szövegek közötti távolság számítására többféle metrikát használhatunk.
• Hamming távolság: az azonos pozícióban lévő, de eltérő betűk száma. Az egyik leggyorsabb algoritmus, a hosszabbik szöveg hosszával arányos időigényű. Használata akkor előnyös, ha egy eltérés felismerése sokkal több megkülönböztető információt hordoz, mint az, hogy ténylegesen hány helyen van eltérés.
def hamming_distance(s1, s2):
diffs = 0
for ch1, ch2 in zip(s1, s2):
if ch1 != ch2:
diffs += 1
return diffs
• Levenshtein távolság: szövegszerkesztési műveletek számában mért távolság, ahol a beszúrás, törlés, és elütés egyforma hibának számít. A távolság Damerau változata a két szomszédos betű felcserélését is egy hibának számolja.
Mindkét algoritmus dinamikus programozási feladatként oldható meg, így legrosszabb esetben a két szöveg hosszának szorzatával arányos időigényű. A természetes szöveghasonlóság számításának alapja. Rövid szövegek, vagy hosszabb, de kevésbé eltérő szövegek esetén alkalmazható. Illetve akkor, ha tudni kell a két szöveg egymásba alakításának pontos módját.
Az egyes szerkesztési műveletek költsége eltérően súlyozható.
def levenshtein_distance(s1,s2):
n, m = len(s1), len(s2)
if n > m:
# Make sure n <= m, to use O(min(n,m)) space
s1,s2 = s2,s1
n,m = m,n
current = range(n+1)
for i in range(1,m+1):
previous, current = current, [i]+[0]*n
for j in range(1,n+1):
add, delete = previous[j]+1, current[j-1]+1
change = previous[j-1]
if s1[j-1] != s2[i-1]:
change = change + 1
current[j] = min(add, delete, change)
return current[n]
• Jaro távolság: az egyező betűk számát, illetve a betűfelcseréléseket veszi figyelembe a távolság számításakor. A lényege, hogy akkor hasonlít jobban két szöveg egymáshoz, ha a rész betűsorozatai megfeleltethetőek egymásnak.
• Hamming távolság: az azonos pozícióban lévő, de eltérő betűk száma. Az egyik leggyorsabb algoritmus, a hosszabbik szöveg hosszával arányos időigényű. Használata akkor előnyös, ha egy eltérés felismerése sokkal több megkülönböztető információt hordoz, mint az, hogy ténylegesen hány helyen van eltérés.
def hamming_distance(s1, s2):
diffs = 0
for ch1, ch2 in zip(s1, s2):
if ch1 != ch2:
diffs += 1
return diffs
• Levenshtein távolság: szövegszerkesztési műveletek számában mért távolság, ahol a beszúrás, törlés, és elütés egyforma hibának számít. A távolság Damerau változata a két szomszédos betű felcserélését is egy hibának számolja.
Mindkét algoritmus dinamikus programozási feladatként oldható meg, így legrosszabb esetben a két szöveg hosszának szorzatával arányos időigényű. A természetes szöveghasonlóság számításának alapja. Rövid szövegek, vagy hosszabb, de kevésbé eltérő szövegek esetén alkalmazható. Illetve akkor, ha tudni kell a két szöveg egymásba alakításának pontos módját.
Az egyes szerkesztési műveletek költsége eltérően súlyozható.
def levenshtein_distance(s1,s2):
n, m = len(s1), len(s2)
if n > m:
# Make sure n <= m, to use O(min(n,m)) space
s1,s2 = s2,s1
n,m = m,n
current = range(n+1)
for i in range(1,m+1):
previous, current = current, [i]+[0]*n
for j in range(1,n+1):
add, delete = previous[j]+1, current[j-1]+1
change = previous[j-1]
if s1[j-1] != s2[i-1]:
change = change + 1
current[j] = min(add, delete, change)
return current[n]
• Jaro távolság: az egyező betűk számát, illetve a betűfelcseréléseket veszi figyelembe a távolság számításakor. A lényege, hogy akkor hasonlít jobban két szöveg egymáshoz, ha a rész betűsorozatai megfeleltethetőek egymásnak.
Kimondottan rövid szövegekre lett kifejlesztve, azon belül is személynevekre. Ráadásul futási időben hasonlítható a dinamikus megoldásokhoz, és a cég, valamint terméknév azonosító szerkezet is hasonló a személynevekhez.
Hátránya, hogy matematikai értelemben véve nem ad metrikát, mert nem teljesül rá a háromszög egyenlőtlenség. Tehát azok az osztályozók, amelyek a távolság eme tulajdonságát használják ki, félreosztályozhatnak.
Az algoritmusnak létezik egy Winkler által definiált továbbfejlesztése, amelyik azon alapul, hogy a szavak elején és végén a betűsorrend helyessége sokkal fontosabb az azonosításkor, mint a közepén. Így a közepén történő különbségeket kisebb súllyal veszi figyelembe.
Az algoritmusnak létezik Java nyelvű szabad implementációja is. A jaro távolság képletében az s1 és s2 a két szöveg hosszát jelöli, az m a megegyező betűk számát, a t pedig a felcserélt betűk számát.
• Ratio hasonlóság: már nem is távolság mérték, hanem egyből hasonlóság. A python difflib csomagjában található SequenceMatcher osztály megvalósítása egy közelítő Leveshntein-féle távolság alapján számolja, míg az algoritmusban alkalmazott változat ennél kicsit nagyobb értékeket ad, hiszen a minimális szövegtávolságra épül.
Ha nincs szükség a minimális szerkesztési távolság meghatározásához, akkor a difflib modul eljárásainak implementációi is használhatóak.
Sőt az ottani megvalósításban gyors-rátát és villám-gyors-rátát is számíttathatunk, melyek a hasonlóságnak egyfajta felső korlátjait adják meg.
Ha nincs szükség a minimális szerkesztési távolság meghatározásához, akkor a difflib modul eljárásainak implementációi is használhatóak.
Sőt az ottani megvalósításban gyors-rátát és villám-gyors-rátát is számíttathatunk, melyek a hasonlóságnak egyfajta felső korlátjait adják meg.
A dekrementális módszerek lényege, hogy az egyes osztályokat csak azután alakítjuk ki, miután már az összes kiemelés párra ismerjük a távolságokat, és ezek alapján jelöljük ki az egymáshoz közeli csomósodásokat, és azok összevonhatóságát.
Ilyenkor egy-egy új elem hozzávétele esetén az osztályok, illetve az azokba történő besorolás jelentősen átalakulhat. Ezért ezek az algoritmusok a távolságok újraszámítása miatt vagy jelentős (négyzetes) időigényűek, vagy ezek tárolása esetén hasonló mértékben tárigényesek.
Akkor érdemes őket alkalmazni, ha az osztályhoz rendelendő új elemek nagyobb adagokban, és nem egyesével érkeznek.
A módszert pontosítani az új elemhez közeli osztályok feldolgozásának sorrendjével és a távolságok újraszámításának hatékonyságával lehet.
https://github.com/klajosw/python/blob/master/kl_python_alapok2.ipynb
mport string
def cleanword(word):
"""
>>> cleanword('what?')
'what'
>>> cleanword('"now!"')
'now'
>>> cleanword('?,;(.-here=@&!)<{')
'here'
>>> cleanword('?+="word!,@$()"')
'word'
"""
word = word.lstrip('\'"?!,;:.+-_=@#$%
return word.rstrip('\'"?!,;:.+-_=@#$%
def has_dashdash(s):
"""
>>> has_dashdash('distance--but')
True
>>> has_dashdash('several')
False
>>> has_dashdash('critters')
False
>>> has_dashdash('spoke--fancy')
True
"""
return '--' in s
def extract_words(s):
"""
>>> extract_words('Now is the time! "Now", is the time? Yes, now.')
['now', 'is', 'the', 'time', 'now', 'is', 'the', 'time', 'yes', 'now']
>>> extract_words('she tried to curtsey as she spoke--fancy')
['she', 'tried', 'to', 'curtsey', 'as', 'she', 'spoke', 'fancy']
"""
s = s.replace('--', ' ')
words = s.split()
for i, word in enumerate(words):
words[i] = cleanword(word).lower()
return words
def wordcount(word, wordlist):
"""
>>> wordcount('now', ['now', 'is', 'time', 'is', 'now', 'is', 'is'])
['now', 2]
>>> wordcount('is', ['now', 'is', 'time', 'is', 'now', 'is', 'the', 'is'])
['is', 4]
>>> wordcount('time', ['now', 'is', 'time', 'is', 'now', 'is', 'is'])
['time', 1]
>>> wordcount('frog', ['now', 'is', 'time', 'is', 'now', 'is', 'is'])
['frog', 0]
"""
return [word, wordlist.count(word), [i for i,x in enumerate(wordlist) if x == word]]
def wordset(wordlist):
"""
>>> wordset(['now', 'is', 'time', 'is', 'now', 'is', 'is'])
['is', 'now', 'time']
>>> wordset(['I', 'a', 'a', 'is', 'a', 'is', 'I', 'am'])
['I', 'a', 'am', 'is']
>>> wordset(['or', 'a', 'am', 'is', 'are', 'be', 'but', 'am'])
['a', 'am', 'are', 'be', 'but', 'is', 'or']
"""
newlist = wordlist[:]
newlist.sort()
uniquewords = []
for word in newlist:
if word not in uniquewords:
uniquewords.append(
return uniquewords
def longestword(wordset):
"""
>>> longestword(['a', 'apple', 'pear', 'grape'])
5
>>> longestword(['a', 'am', 'I', 'be'])
2
>>> longestword(['this', 'that', '
34
"""
infile = open('c:/aa/alice_in_
text = infile.read()
infile.close()
wordlist = extract_words(text)
words = wordset(wordlist)
wordcounts = []
for word in words:
wordcounts.append(wordcount(
outfile = open('c:/aa/alice_in_
outfile.write("%-18s%s\n" % ("Word", "Count"))
outfile.write("===============
for word in wordcounts:
if word[0] and word[0][0] in string.ascii_letters:
outfile.write("%-18s %d -> %30s \n" % (word[0], word[1], word[2]))
# print(",".join(word).tostring(
# outfile.write("%-18s %d\n" (word[0], word[1]))
# outfile.write("%-18s %d s% \n" (word[0], word[1],",".join(word[2])))
##outfile.write("%-18s \n" -18s% ())
outfile.close()
Megjegyzések
Megjegyzés küldése