This Article Full Text Full Text (PDF) Submit a response Alert me when this article is cited Alert me when eLetters are posted Alert me if a correction is posted Services Similar articles in this journal Similar articles in PubMed Alert me to new issues of the journal Download to citation manager Citing Articles Citing Articles via HighWire Citing Articles via Google Scholar Google Scholar Articles by Lovis, C. Articles by Baud, R. H. Search for Related Content PubMed PubMed Citation Articles by Lovis, C. Articles by Baud, R. H.

Fast Exact String Pattern-matching Algorithms Adapted to the Characteristics of the Medical Language

Affiliations of the authors: Puget Sound Health Care System, Seattle, Washington (CL); University Hospital of Geneva, Geneva, Switzerland (RHB).

Correspondence and reprints: Christian Lovis, MD, University Hospital of Geneva, Division of Medical Informatics, Rue Micheli-du-Crest, CH-1211 Geneva 4, Switzerland; e-mail: <christian.lovis{at}dim.hcuge.ch>.

Received for publication: 10/26/99; accepted for publication: 02/16/00.

Abstract Objective: The authors consider the problem of exact string pattern matching using algorithms that do not require any preprocessing. To choose the most appropriate algorithm, distinctive features of the medical language must be taken into account. The characteristics of medical language are emphasized in this regard, the best algorithm of those reviewed is proposed, and detailed evaluations of time complexity for processing medical texts are provided.

Design: The authors first illustrate and discuss the techniques of various string pattern-matching algorithms. Next, the source code and the behavior of representative exact string pattern-matching algorithms are presented in a comprehensive manner to promote their implementation. Detailed explanations of the use of various techniques to improve performance are given.

Measurements: Real-time measures of time complexity with English medical texts are presented. They lead to results distinct from those found in the computer science literature, which are typically computed with normally distributed texts.

Results: The Boyer-Moore-Horspool algorithm achieves the best overall results when used with medical texts. This algorithm usually performs at least twice as fast as the other algorithms tested.

Conclusion: The time performance of exact string pattern matching can be greatly improved if an efficient algorithm is used. Considering the growing amount of text handled in the electronic patient record, it is worth implementing this efficient algorithm.

This article has been cited by other articles:

				O. Uzuner, I. Goldstein, Y. Luo, and I. Kohane Identifying Patient Smoking Status from Medical Discharge Records J. Am. Med. Inform. Assoc., January 1, 2008; 15(1): 14 - 24. [Abstract] [Full Text] [PDF]