Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

Dynamic Edit Distance Table under a General Weighted Cost Function

  • Conference paper
SOFSEM 2010: Theory and Practice of Computer Science (SOFSEM 2010)

Part of the book series: Lecture Notes in Computer Science ((LNTCS,volume 5901))

  • 919 Accesses

Abstract

String comparison is a fundamental task in theoretical computer science, with applications in e.g., spelling correction and computational biology. Edit distance is a classic similarity measure between two given strings A and B. It is the minimum total cost for transforming A into B, or vice versa, using three types of edit operations: single-character insertions, deletions, and/or substitutions.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
USD 29.95
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
USD 84.99
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
USD 109.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. Landau, G.M., Myers, E.W., Schmidt, J.P.: Incremental String Comparison. SIAM J. Comp. 27(2), 557–582 (1998)

    Article  MATH  MathSciNet  Google Scholar 

  2. Schmidt, J.P.: All Highest Scoring Paths in Weighted Grid Graphs and Their Application in Finding All Approximate Repeats in Strings. SIAM J. Comp. 27(4), 972–992 (1998)

    Article  MATH  Google Scholar 

  3. Kim, S.R., Park, K.: A Dynamic Edit Distance Table. J. Disc. Algo. 2, 302–312 (2004)

    Google Scholar 

  4. Hyyrö, H.: An Efficient Linear Space Algorithm for Consecutive Suffix Alignment under Edit Distance. In: Amir, A., Turpin, A., Moffat, A. (eds.) SPIRE 2008. LNCS, vol. 5280, pp. 155–163. Springer, Heidelberg (2008)

    Chapter  Google Scholar 

  5. Masek, W.J., Paterson, M.: A Faster Algorithm Computing String Edit Distances. J. Comput. Syst. Sci. 20(1), 18–31 (1980)

    Article  MATH  MathSciNet  Google Scholar 

  6. Arnold, R., Bell, T.: A Corpus for the Evaluation of Lossless Compression Algorithms. In: Proc. DCC 1997, pp. 201–210 (1997), http://corpus.canterbury.ac.nz/

  7. Kurtz, S.: Approximate String Searching under Weighted Edit Distance. In: Proc. 3rd South American Workshop on String Processing (WSP 1996), pp. 156–170 (1996)

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Computer Sciences, University of Tampere, Finland

    Heikki Hyyrö

  2. Department of Informatics, Kyushu University, Japan

    Kazuyuki Narisawa

  3. Japan Society for the Promotion of Science (JSPS),  

    Kazuyuki Narisawa

  4. Graduate School of Information Sci. and Electrical Eng., Kyushu University, Japan

    Shunsuke Inenaga

Authors
  1. Heikki Hyyrö
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Kazuyuki Narisawa
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Shunsuke Inenaga
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Editors and Affiliations

  1. Department of Information and Computing Sciences, Utrecht University, Padualaan 14, 3584 CH, Utrecht, The Netherlands

    Jan van Leeuwen

  2. LaBRI, Universit Bordeaux, 351 cours de la Libration, 1F-33405, Talence Cedex, France

    Anca Muscholl

  3. Department of Computer Science & Applied Mathematics, Weizmann Institute, Faculty of Mathematics and Computer Science, 76100, Rehovot, Israel

    David Peleg

  4. Department of Software Engineering Faculty of Mathematics and Physics Malostranské nám, Charles University, 25 11800, Prague 1, Czech Republic

    Jaroslav Pokorný

  5. Software Engineering, Department of Computer Science, RWTH Aachen University, 3, Ahornstrae 55, D-52074, Aachen, Germany

    Bernhard Rumpe

Rights and permissions

Reprints and permissions

Copyright information

© 2010 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Hyyrö, H., Narisawa, K., Inenaga, S. (2010). Dynamic Edit Distance Table under a General Weighted Cost Function. In: van Leeuwen, J., Muscholl, A., Peleg, D., Pokorný, J., Rumpe, B. (eds) SOFSEM 2010: Theory and Practice of Computer Science. SOFSEM 2010. Lecture Notes in Computer Science, vol 5901. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-11266-9_43

Download citation

  • DOI: https://doi.org/10.1007/978-3-642-11266-9_43

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-642-11265-2

  • Online ISBN: 978-3-642-11266-9

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation