Minimālā rediģēšanas distance

Pēdējais mainījis Administrator 2011-06-06 17:14

Minimālā rediģēšanas distance

Noskaidrot kurš no dieviem vārdiem ir tuvāks kādam trešajam vārdam ir speciāls gadījums no vispārīgās simbolu virkņu (81) problēmas. Attālums starp divām simbolu virknēm ir mērs, ar kuru tiek mērīta līdzība starp simbolu virknēm.

Daudzi algoritmi attālumu meklēšanai starp simbolu virknēm ir balstīti uz vienu no minimālās rediģēšanas attāluma algoritma versijām, kas tika nosauktas par godu Vāgneram (Wagner) un Fišeram (Fischer) (83), bet tika izgudrotas arī neatkarīgas versijas, kā vienu no tādiem varētu minēt Levenšteina (Levenshtein) algoritmu (82).

Minimālais rediģēšanas attālums ir starp divām simbolu virknēm ir minimālais operāciju (ievietošana, dzēšana, aizvietošana) skaits, kas nepieciešams, lai pārveidotu vienu simbolu virkni par citu.

Pastāv dažādi, publiski pieejami risinājumi rediģēšanas attāluma skaitļošanai, piemēram, UNIX diff (85) un NIST sclite (84).

Atpakaļ uz saturu

Tagi:
Izveidojis MarisSteinbergs 2007-12-30 19:46
    
This wiki is licensed under a Creative Commons 2.0 license
XWiki Enterprise 6.4 - Documentation