ლევენშტეინის მანძილი
ლევენშტეინის მანძილი ან ცვლილებათა მანძილი — ოპერაციების მინიმალური რაოდენობა ერთი სტრიქონის მეორე სტრიქონამდე შეცვლისთვის. ოპერაციები შემდეგია: სიმბოლოს ჩამატება (მაგ. "აბგ" >"აბგა"), სიმბოლოს წაშლა (მაგ. "აბგ"->"აგ") და სიმბოლოს შეცვლა (მაგ. "აბგ"->"ადგ"). მაგალითად, ცვლილებათა მანძილი "თეორემა" -> "თეორია" არის 2, ცვლილებები შემდეგია: "თეორემა" -> "თეორმა" (წაშლა), შემდეგ "თეორმა"->"თეორია" (ჩანაცვლება). დავუშვათ, მოცემულია n {\displaystyle n} სიგრძის სტრიქონი x {\displaystyle x} და m {\displaystyle m} სიგრძის სტრიქონი y {\displaystyle y} და გვინდა გამოვთვალოთ ცვლილებათა მანძილი ამ სტრიქონებს შორის. ამის ამოსახსნელად, შემოვიღოთ ფუნქცია d i s t a n c e ( a , b ) {\displaystyle distance(a,b)} , რომელიც გვიბრუნებს ცვლილებათა მანძილს პრეფიქსების, x [ 0... a {\displaystyle x[0...a} ] და y [ 0... b ] {\displaystyle y[0...b]} , შორის. ამ ფუნქციის გამოყენებით ლევენშტეინის მანძილი x {\displaystyle x} და y {\displaystyle y} სტრიქონებს შორის არის d i s t a n c e ( n − 1 , m − 1 ) {\displaystyle distance(n-1,m-1)} . ფუნქცია გამოიყურება შემდეგნაირად d i s t a n c e ( a , b ) = m i n ( d i s t a n c e ( a , b − 1 ) + 1 , d i s t a n c e ( a − 1 , b ) + 1 , d i s t a n c e ( a − 1 , b − 1 ) + c o s t ( a , b ) ) . {\displaystyle distance(a,b)=min(distance(a,b-1)+1,distance(a-1,b)+1,distance(a-1,b-1)+cost(a,b)).} აქ c o s t ( a , b ) = 0 {\displaystyle cost(a,b)=0} , თუ x [ a ] = y [ b ] {\displaystyle x[a]=y[b]} , თუ არა, c o s t ( a , b ) = 1 {\displaystyle cost(a,b)=1} . x {\displaystyle x} სტრიქონის შეცვლისთვის ფორმულა განიმარტება შემდეგნაირად: d i s t a n c e ( a , b − 1 ) {\displaystyle distance(a,b-1)} : x {\displaystyle x} სტრიქონის ბოლოში სიმბოლოს ჩამატება d i s t a n c e ( a − 1 , b ) {\displaystyle distance(a-1,b)} : x {\displaystyle x} სტრიქონის ბოლო სიმბოლოს წაშლა d i s t a n c e ( a − 1 , b − 1 ) {\displaystyle distance(a-1,b-1)} : x {\displaystyle x} სტრიქონის ბოლო სიმბოლოს დამთხვევა ან შეცვლა.