Fast computation of normalized edit distances
Identifieur interne : 002C04 ( Main/Exploration ); précédent : 002C03; suivant : 002C05Fast computation of normalized edit distances
Auteurs : E. Vidal ; A. Marzal ; P. AibarSource :
- IEEE Transactions on Pattern Analysis and Machine Intelligence [ 0162-8828 ] ; 1995.
Descripteurs français
- Pascal (Inist)
English descriptors
- KwdEn :
- Algorithms, Application, Calculations, Character recognition, Computational complexity, Fast algorithms, Fractional programming, Levenslatein distance, Normalized edit distance, Optical character recognition, Optimization, Pattern recognition, Speech recognition, Spelling correction, String correction, Theory.
Abstract
The Normalized Edit Distance (NED) between two strings X and Y is defined as the minimum quotient between the sum of weights of the edit operations required to transform X into Y and the length of the editing path corresponding to these operations. An algorithm for computing the NED has recently been introduced by Marzal and Vidal that exhibits O(mn2) computing complexity, where m and n are the lengths of X and Y. We propose here an algorithm that is observed to require in practice the same O(mn) computing resources as the conventional unnormalized Edit Distance algorithm does. The performance of this algorithm is illustrated through computational experiments with synthetic data, as well as with real data consisting of OCR chain-coded strings.
Affiliations:
Links toward previous steps (curation, corpus...)
- to stream PascalFrancis, to step Corpus: 000A46
- to stream PascalFrancis, to step Curation: 000953
- to stream PascalFrancis, to step Checkpoint: 000A12
- to stream Main, to step Merge: 002D65
- to stream Main, to step Curation: 002C04
Le document en format XML
<record><TEI><teiHeader><fileDesc><titleStmt><title xml:lang="en" level="a">Fast computation of normalized edit distances</title><author><name sortKey="Vidal, E" sort="Vidal, E" uniqKey="Vidal E" first="E." last="Vidal">E. Vidal</name><affiliation><inist:fA14 i1="01"><s1>Universidad Politecnica de Valencia</s1><s3>INC</s3><sZ>1 aut.</sZ></inist:fA14><wicri:noCountry>INC</wicri:noCountry></affiliation></author><author><name sortKey="Marzal, A" sort="Marzal, A" uniqKey="Marzal A" first="A." last="Marzal">A. Marzal</name></author><author><name sortKey="Aibar, P" sort="Aibar, P" uniqKey="Aibar P" first="P." last="Aibar">P. Aibar</name></author></titleStmt><publicationStmt><idno type="wicri:source">INIST</idno><idno type="inist">95-0527486</idno><date when="1995">1995</date><idno type="stanalyst">PASCAL 95-0527486 EI</idno><idno type="RBID">Pascal:95-0527486</idno><idno type="wicri:Area/PascalFrancis/Corpus">000A46</idno><idno type="wicri:Area/PascalFrancis/Curation">000953</idno><idno type="wicri:Area/PascalFrancis/Checkpoint">000A12</idno><idno type="wicri:doubleKey">0162-8828:1995:Vidal E:fast:computation:of</idno><idno type="wicri:Area/Main/Merge">002D65</idno><idno type="wicri:Area/Main/Curation">002C04</idno><idno type="wicri:Area/Main/Exploration">002C04</idno></publicationStmt><sourceDesc><biblStruct><analytic><title xml:lang="en" level="a">Fast computation of normalized edit distances</title><author><name sortKey="Vidal, E" sort="Vidal, E" uniqKey="Vidal E" first="E." last="Vidal">E. Vidal</name><affiliation><inist:fA14 i1="01"><s1>Universidad Politecnica de Valencia</s1><s3>INC</s3><sZ>1 aut.</sZ></inist:fA14><wicri:noCountry>INC</wicri:noCountry></affiliation></author><author><name sortKey="Marzal, A" sort="Marzal, A" uniqKey="Marzal A" first="A." last="Marzal">A. Marzal</name></author><author><name sortKey="Aibar, P" sort="Aibar, P" uniqKey="Aibar P" first="P." last="Aibar">P. Aibar</name></author></analytic><series><title level="j" type="main">IEEE Transactions on Pattern Analysis and Machine Intelligence</title><title level="j" type="abbreviated">IEEE Trans Pattern Anal Mach Intell</title><idno type="ISSN">0162-8828</idno><imprint><date when="1995">1995</date></imprint></series></biblStruct></sourceDesc><seriesStmt><title level="j" type="main">IEEE Transactions on Pattern Analysis and Machine Intelligence</title><title level="j" type="abbreviated">IEEE Trans Pattern Anal Mach Intell</title><idno type="ISSN">0162-8828</idno></seriesStmt></fileDesc><profileDesc><textClass><keywords scheme="KwdEn" xml:lang="en"><term>Algorithms</term><term>Application</term><term>Calculations</term><term>Character recognition</term><term>Computational complexity</term><term>Fast algorithms</term><term>Fractional programming</term><term>Levenslatein distance</term><term>Normalized edit distance</term><term>Optical character recognition</term><term>Optimization</term><term>Pattern recognition</term><term>Speech recognition</term><term>Spelling correction</term><term>String correction</term><term>Theory</term></keywords><keywords scheme="Pascal" xml:lang="fr"><term>Application</term><term>Reconnaissance forme</term><term>Reconnaissance caractère</term><term>Reconnaissance parole</term><term>Complexité calcul</term><term>Optimisation</term><term>Calcul</term><term>Reconnaissance optique caractère</term><term>Algorithme</term><term>Théorie</term></keywords></textClass></profileDesc></teiHeader><front><div type="abstract" xml:lang="en">The Normalized Edit Distance (NED) between two strings X and Y is defined as the minimum quotient between the sum of weights of the edit operations required to transform X into Y and the length of the editing path corresponding to these operations. An algorithm for computing the NED has recently been introduced by Marzal and Vidal that exhibits O(mn<sup>2</sup>) computing complexity, where m and n are the lengths of X and Y. We propose here an algorithm that is observed to require in practice the same O(mn) computing resources as the conventional unnormalized Edit Distance algorithm does. The performance of this algorithm is illustrated through computational experiments with synthetic data, as well as with real data consisting of OCR chain-coded strings.</div></front></TEI><affiliations><list></list><tree><noCountry><name sortKey="Aibar, P" sort="Aibar, P" uniqKey="Aibar P" first="P." last="Aibar">P. Aibar</name><name sortKey="Marzal, A" sort="Marzal, A" uniqKey="Marzal A" first="A." last="Marzal">A. Marzal</name><name sortKey="Vidal, E" sort="Vidal, E" uniqKey="Vidal E" first="E." last="Vidal">E. Vidal</name></noCountry></tree></affiliations></record>Pour manipuler ce document sous Unix (Dilib)
EXPLOR_STEP=$WICRI_ROOT/Ticri/CIDE/explor/OcrV1/Data/Main/Exploration
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 002C04 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/Main/Exploration/biblio.hfd -nk 002C04 | SxmlIndent | more
Pour mettre un lien sur cette page dans le réseau Wicri
{{Explor lien
|wiki= Ticri/CIDE
|area= OcrV1
|flux= Main
|étape= Exploration
|type= RBID
|clé= Pascal:95-0527486
|texte= Fast computation of normalized edit distances
}}
| This area was generated with Dilib version V0.6.32. |  |