OcrV1, PascalFrancis, Corpus, bibRecord, 000A46

Fast computation of normalized edit distances

Identifieur interne : 000A46 ( PascalFrancis/Corpus ); précédent : 000A45; suivant : 000A47

Fast computation of normalized edit distances

Auteurs : E. Vidal ; A. Marzal ; P. Aibar

Source :

IEEE Transactions on Pattern Analysis and Machine Intelligence [ 0162-8828 ] ; 1995.

RBID : Pascal:95-0527486

Descripteurs français

Pascal (Inist)
- Application, Reconnaissance forme, Reconnaissance caractère, Reconnaissance parole, Complexité calcul, Optimisation, Calcul, Reconnaissance optique caractère, Algorithme, Théorie.

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(mn²) 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.

Notice en format standard (ISO 2709)

Pour connaître la documentation sur le format Inist Standard.

A01	`01`	`1`		`@0 0162-8828`
A02	`01`			`@0 ITPIDJ`
A03		`1`		`@0 IEEE Trans Pattern Anal Mach Intell`
A05				`@2 17`
A06				`@2 9`
A08	`01`	`1`	`ENG`	`@1 Fast computation of normalized edit distances`
A11	`01`	`1`		`@1 VIDAL (E.)`
A11	`02`	`1`		`@1 MARZAL (A.)`
A11	`03`	`1`		`@1 AIBAR (P.)`
A14	`01`			`@1 Universidad Politecnica de Valencia @3 INC @Z 1 aut.`
A20				`@1 899-902`
A21				`@1 1995`
A23	`01`			`@0 ENG`
A43	`01`			`@1 INIST @2 222 T`
A44				`@0 A100`
A45				`@0 12 Refs.`
A47	`01`	`1`		`@0 95-0527486`
A60				`@1 P`
A61				`@0 A`
A64	`01`	`1`		`@0 IEEE Transactions on Pattern Analysis and Machine Intelligence`
A66	`01`			`@0 USA`
C01	`01`		`ENG`	@0 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²) 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.
C02	`01`	`1`		`@0 001D02C`
C02	`02`	`1`		`@0 001D02A`
C02	`03`	`1`		`@0 001D01A`
C02	`04`	`1`		`@0 001A02I01`
C03	`01`	`1`	`ENG`	`@0 Normalized edit distance @4 INC`
C03	`02`	`1`	`ENG`	`@0 Levenslatein distance @4 INC`
C03	`03`	`1`	`ENG`	`@0 String correction @4 INC`
C03	`04`	`1`	`ENG`	`@0 Spelling correction @4 INC`
C03	`05`	`1`	`ENG`	`@0 Fractional programming @4 INC`
C03	`06`	`1`	`ENG`	`@0 Fast algorithms @4 INC`
C03	`07`	`X`	`FRE`	`@0 Application`
C03	`07`	`X`	`ENG`	`@0 Application`
C03	`07`	`X`	`GER`	`@0 Anwendung`
C03	`07`	`X`	`SPA`	`@0 Aplicación`
C03	`08`	`1`	`FRE`	`@0 Reconnaissance forme`
C03	`08`	`1`	`ENG`	`@0 Pattern recognition`
C03	`09`	`1`	`FRE`	`@0 Reconnaissance caractère`
C03	`09`	`1`	`ENG`	`@0 Character recognition`
C03	`10`	`1`	`FRE`	`@0 Reconnaissance parole`
C03	`10`	`1`	`ENG`	`@0 Speech recognition`
C03	`11`	`1`	`FRE`	`@0 Complexité calcul`
C03	`11`	`1`	`ENG`	`@0 Computational complexity`
C03	`12`	`1`	`FRE`	`@0 Optimisation`
C03	`12`	`1`	`ENG`	`@0 Optimization`
C03	`13`	`1`	`FRE`	`@0 Calcul`
C03	`13`	`1`	`ENG`	`@0 Calculations`
C03	`14`	`1`	`FRE`	`@0 Reconnaissance optique caractère`
C03	`14`	`1`	`ENG`	`@0 Optical character recognition`
C03	`15`	`1`	`FRE`	`@0 Algorithme @3 P`
C03	`15`	`1`	`ENG`	`@0 Algorithms @3 P`
C03	`16`	`1`	`FRE`	`@0 Théorie`
C03	`16`	`1`	`ENG`	`@0 Theory`
N21				`@1 302`

Format Inist (serveur)

NO :	PASCAL 95-0527486 EI
ET :	Fast computation of normalized edit distances
AU :	VIDAL (E.); MARZAL (A.); AIBAR (P.)
AF :	Universidad Politecnica de Valencia/Inconnu (1 aut.)
DT :	Publication en série; Niveau analytique
SO :	IEEE Transactions on Pattern Analysis and Machine Intelligence; ISSN 0162-8828; Coden ITPIDJ; Etats-Unis; Da. 1995; Vol. 17; No. 9; Pp. 899-902; Bibl. 12 Refs.
LA :	Anglais
EA :	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²) 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.
CC :	001D02C; 001D02A; 001D01A; 001A02I01
FD :	Application; Reconnaissance forme; Reconnaissance caractère; Reconnaissance parole; Complexité calcul; Optimisation; Calcul; Reconnaissance optique caractère; Algorithme; Théorie
ED :	Normalized edit distance; Levenslatein distance; String correction; Spelling correction; Fractional programming; Fast algorithms; Application; Pattern recognition; Character recognition; Speech recognition; Computational complexity; Optimization; Calculations; Optical character recognition; Algorithms; Theory
GD :	Anwendung
SD :	Aplicación
LO :	INIST-222 T
ID :	95-0527486

Links to Exploration step

Pascal:95-0527486

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>
</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>
</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>
</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>
<inist><standard h6="B"><pA><fA01 i1="01" i2="1"><s0>0162-8828</s0>
</fA01>
<fA02 i1="01"><s0>ITPIDJ</s0>
</fA02>
<fA03 i2="1"><s0>IEEE Trans Pattern Anal Mach Intell</s0>
</fA03>
<fA05><s2>17</s2>
</fA05>
<fA06><s2>9</s2>
</fA06>
<fA08 i1="01" i2="1" l="ENG"><s1>Fast computation of normalized edit distances</s1>
</fA08>
<fA11 i1="01" i2="1"><s1>VIDAL (E.)</s1>
</fA11>
<fA11 i1="02" i2="1"><s1>MARZAL (A.)</s1>
</fA11>
<fA11 i1="03" i2="1"><s1>AIBAR (P.)</s1>
</fA11>
<fA14 i1="01"><s1>Universidad Politecnica de Valencia</s1>
<s3>INC</s3>
<sZ>1 aut.</sZ>
</fA14>
<fA20><s1>899-902</s1>
</fA20>
<fA21><s1>1995</s1>
</fA21>
<fA23 i1="01"><s0>ENG</s0>
</fA23>
<fA43 i1="01"><s1>INIST</s1>
<s2>222 T</s2>
</fA43>
<fA44><s0>A100</s0>
</fA44>
<fA45><s0>12 Refs.</s0>
</fA45>
<fA47 i1="01" i2="1"><s0>95-0527486</s0>
</fA47>
<fA60><s1>P</s1>
</fA60>
<fA61><s0>A</s0>
</fA61>
<fA64 i1="01" i2="1"><s0>IEEE Transactions on Pattern Analysis and Machine Intelligence</s0>
</fA64>
<fA66 i1="01"><s0>USA</s0>
</fA66>
<fC01 i1="01" l="ENG"><s0>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.</s0>
</fC01>
<fC02 i1="01" i2="1"><s0>001D02C</s0>
</fC02>
<fC02 i1="02" i2="1"><s0>001D02A</s0>
</fC02>
<fC02 i1="03" i2="1"><s0>001D01A</s0>
</fC02>
<fC02 i1="04" i2="1"><s0>001A02I01</s0>
</fC02>
<fC03 i1="01" i2="1" l="ENG"><s0>Normalized edit distance</s0>
<s4>INC</s4>
</fC03>
<fC03 i1="02" i2="1" l="ENG"><s0>Levenslatein distance</s0>
<s4>INC</s4>
</fC03>
<fC03 i1="03" i2="1" l="ENG"><s0>String correction</s0>
<s4>INC</s4>
</fC03>
<fC03 i1="04" i2="1" l="ENG"><s0>Spelling correction</s0>
<s4>INC</s4>
</fC03>
<fC03 i1="05" i2="1" l="ENG"><s0>Fractional programming</s0>
<s4>INC</s4>
</fC03>
<fC03 i1="06" i2="1" l="ENG"><s0>Fast algorithms</s0>
<s4>INC</s4>
</fC03>
<fC03 i1="07" i2="X" l="FRE"><s0>Application</s0>
</fC03>
<fC03 i1="07" i2="X" l="ENG"><s0>Application</s0>
</fC03>
<fC03 i1="07" i2="X" l="GER"><s0>Anwendung</s0>
</fC03>
<fC03 i1="07" i2="X" l="SPA"><s0>Aplicación</s0>
</fC03>
<fC03 i1="08" i2="1" l="FRE"><s0>Reconnaissance forme</s0>
</fC03>
<fC03 i1="08" i2="1" l="ENG"><s0>Pattern recognition</s0>
</fC03>
<fC03 i1="09" i2="1" l="FRE"><s0>Reconnaissance caractère</s0>
</fC03>
<fC03 i1="09" i2="1" l="ENG"><s0>Character recognition</s0>
</fC03>
<fC03 i1="10" i2="1" l="FRE"><s0>Reconnaissance parole</s0>
</fC03>
<fC03 i1="10" i2="1" l="ENG"><s0>Speech recognition</s0>
</fC03>
<fC03 i1="11" i2="1" l="FRE"><s0>Complexité calcul</s0>
</fC03>
<fC03 i1="11" i2="1" l="ENG"><s0>Computational complexity</s0>
</fC03>
<fC03 i1="12" i2="1" l="FRE"><s0>Optimisation</s0>
</fC03>
<fC03 i1="12" i2="1" l="ENG"><s0>Optimization</s0>
</fC03>
<fC03 i1="13" i2="1" l="FRE"><s0>Calcul</s0>
</fC03>
<fC03 i1="13" i2="1" l="ENG"><s0>Calculations</s0>
</fC03>
<fC03 i1="14" i2="1" l="FRE"><s0>Reconnaissance optique caractère</s0>
</fC03>
<fC03 i1="14" i2="1" l="ENG"><s0>Optical character recognition</s0>
</fC03>
<fC03 i1="15" i2="1" l="FRE"><s0>Algorithme</s0>
<s3>P</s3>
</fC03>
<fC03 i1="15" i2="1" l="ENG"><s0>Algorithms</s0>
<s3>P</s3>
</fC03>
<fC03 i1="16" i2="1" l="FRE"><s0>Théorie</s0>
</fC03>
<fC03 i1="16" i2="1" l="ENG"><s0>Theory</s0>
</fC03>
<fN21><s1>302</s1>
</fN21>
</pA>
</standard>
<server><NO>PASCAL 95-0527486 EI</NO>
<ET>Fast computation of normalized edit distances</ET>
<AU>VIDAL (E.); MARZAL (A.); AIBAR (P.)</AU>
<AF>Universidad Politecnica de Valencia/Inconnu (1 aut.)</AF>
<DT>Publication en série; Niveau analytique</DT>
<SO>IEEE Transactions on Pattern Analysis and Machine Intelligence; ISSN 0162-8828; Coden ITPIDJ; Etats-Unis; Da. 1995; Vol. 17; No. 9; Pp. 899-902; Bibl. 12 Refs.</SO>
<LA>Anglais</LA>
<EA>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.</EA>
<CC>001D02C; 001D02A; 001D01A; 001A02I01</CC>
<FD>Application; Reconnaissance forme; Reconnaissance caractère; Reconnaissance parole; Complexité calcul; Optimisation; Calcul; Reconnaissance optique caractère; Algorithme; Théorie</FD>
<ED>Normalized edit distance; Levenslatein distance; String correction; Spelling correction; Fractional programming; Fast algorithms; Application; Pattern recognition; Character recognition; Speech recognition; Computational complexity; Optimization; Calculations; Optical character recognition; Algorithms; Theory</ED>
<GD>Anwendung</GD>
<SD>Aplicación</SD>
<LO>INIST-222 T</LO>
<ID>95-0527486</ID>
</server>
</inist>
</record>

Pour manipuler ce document sous Unix (Dilib)

EXPLOR_STEP=$WICRI_ROOT/Ticri/CIDE/explor/OcrV1/Data/PascalFrancis/Corpus

HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 000A46 | SxmlIndent | more

HfdSelect -h $EXPLOR_AREA/Data/PascalFrancis/Corpus/biblio.hfd -nk 000A46 | SxmlIndent | more

Pour mettre un lien sur cette page dans le réseau Wicri

{{Explor lien
   |wiki=    Ticri/CIDE
   |area=    OcrV1
   |flux=    PascalFrancis
   |étape=   Corpus
   |type=    RBID
   |clé=     Pascal:95-0527486
   |texte=   Fast computation of normalized edit distances
}}

This area was generated with Dilib version V0.6.32.
Data generation: Sat Nov 11 16:53:45 2017. Site generation: Mon Mar 11 23:15:16 2024

	Serveur d'exploration sur l'OCR
	Attention, ce site est en cours de développement ! Attention, site généré par des moyens informatiques à partir de corpus bruts. Les informations ne sont donc pas validées.

Serveur d'exploration sur l'OCR

Fast computation of normalized edit distances

Fast computation of normalized edit distances

Source :

Descripteurs français

English descriptors

Abstract

Notice en format standard (ISO 2709)

Format Inist (serveur)

Links to Exploration step

Le document en format XML

Pour manipuler ce document sous Unix (Dilib)

Pour mettre un lien sur cette page dans le réseau Wicri