Text distance

Terveztem egy eljárást két szöveg hasonlóságának vizsgálatára. Gyorsabb mint a Levenshtein távolság (lineáris időben fut) és más karakterisztikákkal rendelkezik. Előbbihez lásd:

https://en.wikipedia.org/wiki/Levenshtein_distance

Egy matematikai pontszámot állapítok meg, melynél minél kisebb érték minél nagyobb egyezést jelent. A legkisebb érték a nulla, ahol teljes az egyezés.

Megoldásom (Ruby):

def text_distance( text1, text2 )
	# remove capitals and accents
	text1 = remove_accent( text1.downcase )
	text2 = remove_accent( text2.downcase )
	# get differences of neighbouring char codes
	t1 = text1.chars.map(&:ord).each_cons(2).map{|c1,c2| ( c1 - c2 ) }
	t2 = text2.chars.map(&:ord).each_cons(2).map{|c1,c2| ( c1 - c2 ) }
	# correction if text consists of a single char
	t1 = [text1.ord]  if t1.size == 0
	t2 = [text2.ord]  if t2.size == 0
	# apply different stats and score it
	score = 0
	[ t1.size, t2.size,
	  dmean(t1), dmean(t2),
	  dstd(t1), dstd(t2),
	  dskewness(t1), dskewness(t2) ].each_slice(2){|v1,v2|
		score += Math.log( ( v1 - v2 ).abs + 1 )
	}
	return score
end

Hiányzó külső függvények magyarázata:

- remove_accent eltávolítja az ékezeteket

- dmean az 1 dimenziós tömb aritmetikai átlagát adja vissza

- dstd ugyanígy normál szórás

- dskewness ugyanígy normál ferdeség

A statisztikai tulajdonságoknál az átlag és a szórás úgymond "szimmetrikus" (sorrend független), ezért könnyebben előfordulhatna ütközés, vagyis ugyanolyan pontszám, ha radikálisan más szöveghez hasonlítjuk az elsőt. A skewness viszont segít ennek a "szimmetriának" a feloldásában. Rengeteg további stat alkalmazható még, mely további szemüvegen keresztül nézi az adott string-et. Ez jövőbeli kutatásom részét képezi.

Példák:

hello / hello = 0

hello / hellx = 2.44

hello / hell = 2.25

hello / ello = 2.33

hello / hellooooo = 3.79

hello / ciao = 4.66

monday / friday = 2.05

monday / dayfri = 3.31

monday / daymon = 0.934

1234567 / 7654321 = 1.1

1234567 / 1234576 = 1.73

1234567 / 12345678 = 0.693

árvíztűrő tükörfúrógép / lorem ipsum = 5.6

árvíztűrő tükörfúrógép / lorem tükör ipsum = 5.22

lorem ipsum / lorem tükör ipsum = 3.99

...

sinexton blogja
A hozzászóláshoz be kell jelentkezni

Ezt a bácsit ismerem :) Én is használtam, mikor külső "kézi" excelt kellett adatbázissal összekapcsolni, hogy az elírások nagy részét le tudjam kezelni.

0 szavazat

A hozzászóláshoz be kell jelentkezni

Milyen hasznos. Ötletes és könnyen érthető eljárás. Mindig rácsodálkozok, hogy mennyi matematikai alterület mekkora úttörő munkája milyen régen történt, rengeteg az 1700-as és 1800-as években.

0 szavazat

A hozzászóláshoz be kell jelentkezni

Újabb megoldásom, ahol megvizsgálom az összes substring kombinációt és hosszabb substring egyezéseket négyzetesen magasabban pontozok. Illetve büntetem a hossz különbséget.

Ennek további előnye a fentiekkel szemben, hogy nincs "ütközés", ahol teljesen más string ugyanolyan jó eredményt adhat. Illetve kicsit okosabb mint Levenshtein distance, mert különbséget tesz az alábbi párok között (kisebb pontszám jobb egyezést jelent):

monday / dayfri = 6 (Levenshtein distance)

monday / daymon = 6 (Levenshtein distance)

monday / dayfri = 2.24

monday / daymon = 1.57

Tehát a megoldásom érzékeli a "mon" substring meglétét az utolsóban és ezért kisebb hibára pontozza.

Két függvényt írtam. Az elsőnél a nagyobb pontszám a jobb egyezés, de ez felülről határos. És más stringeknél máshol van ez a határ. Ezért megállapítom a teljes egyezés pontszámát, majd ehhez képest normalizálom az eredményt úgy, hogy ez adja a nullát és az ettől eltérő nagyobb pontszám fog jelenteni kisebb egyezést.

# return a relative score showing text similarity
# count the matches of the different substring combinations with different lengths
# score longer substrings higher
# match is better if score is higher
# runtime is quadratic
def text_distance_helper( text1, text2 )
	# remove capitals and accents
	text1 = remove_accent( text1.downcase )
	text2 = remove_accent( text2.downcase )
	# collect chars
	t1 = text1.chars
	t2 = text2.chars
	# create score
	sum = 0
	(1..t1.size).each {|i|
		# get unique substring combinations for length i
		t2x = t2.each_cons(i).uniq
		# count substring matches
		count = 0
		t1.each_cons(i).uniq.each{|x|
			count += t2x.count(x)
		}
		# score higher longer substring matches with a square
		sum += i**2 * count
	}
	# penalize length difference
	score = Math.log( sum + 1 ) - Math.log(( t1.size - t2.size ).abs + 1 )
	return score
end

# compute match score and normalize it by shifting it to zero and changing sign
# so lower score is better where zero means perfect match
def text_distance( text1, text2 )
	score_max = text_distance_helper( text1, text1 )
	score = text_distance_helper( text1, text2 )
	score -= score_max
	score *= -1
	score = 0  if score == 0.0
	return score
end

Ez az implementáció négyzetes idejű és sokkal lassabb a fenti kettőnél. További optimalizálás szükséges.

0 szavazat

A hozzászóláshoz be kell jelentkezni

Közben sikerült 3-szor gyorsabbra optimalizálnom. Ez még nem elég, de előrelépés. A sebessége 1 szálon egy modern gépen másodpercenként 5100 számítás 10 karakteres szövegeken.

Vonatkozó kódrész:

(1..t1.size).each {|i|
	# get unique substring combinations for length i
	# the intersection method will make the result list unique
	# so no need to use uniq on them
	# score higher longer substring matches with a square
	sum += i**2 * t1.each_cons(i).to_a.intersection( t2.each_cons(i).to_a ).size
}

0 szavazat