THE EXTENDED BOYER-MOORE-HORSPOOL ALGORITHM FOR LOCALITY-SENSITIVE PSEUDO-CODE

Kengo Terasawa, Toshio Kawashima, Yuzuru Tanaka

2011

Abstract

Boyer-Moore-Horspool (BMH) algorithm is known as a very efficient algorithm that finds a place where a certain string specified by the user appears within a longer text string. In this study, we propose the Extended Boyer-Moore-Horspool algorithm that can retrieve a pattern in the sequence of real vectors, rather than in the sequence of the characters. We reproduced the BMH algorithm to the sequence of real vectors by transforming the vectors into pseudo-code expression that consists of multiple integers and by introducing a novel binary relation called ‘semiequivalent.’ We confirmed the practical utility of our algorithm by applying it to the string matching problem of the images from “Minutes of the Imperial Diet,” to which optical character recognition does not work well.

Download


Paper Citation


in Harvard Style

Terasawa K., Kawashima T. and Tanaka Y. (2011). THE EXTENDED BOYER-MOORE-HORSPOOL ALGORITHM FOR LOCALITY-SENSITIVE PSEUDO-CODE . In Proceedings of the International Conference on Computer Vision Theory and Applications - Volume 1: VISAPP, (VISIGRAPP 2011) ISBN 978-989-8425-47-8, pages 437-441. DOI: 10.5220/0003369004370441

in Bibtex Style

@conference{visapp11,
author={Kengo Terasawa and Toshio Kawashima and Yuzuru Tanaka},
title={THE EXTENDED BOYER-MOORE-HORSPOOL ALGORITHM FOR LOCALITY-SENSITIVE PSEUDO-CODE},
booktitle={Proceedings of the International Conference on Computer Vision Theory and Applications - Volume 1: VISAPP, (VISIGRAPP 2011)},
year={2011},
pages={437-441},
publisher={SciTePress},
organization={INSTICC},
doi={10.5220/0003369004370441},
isbn={978-989-8425-47-8},
}


in EndNote Style

TY - CONF
JO - Proceedings of the International Conference on Computer Vision Theory and Applications - Volume 1: VISAPP, (VISIGRAPP 2011)
TI - THE EXTENDED BOYER-MOORE-HORSPOOL ALGORITHM FOR LOCALITY-SENSITIVE PSEUDO-CODE
SN - 978-989-8425-47-8
AU - Terasawa K.
AU - Kawashima T.
AU - Tanaka Y.
PY - 2011
SP - 437
EP - 441
DO - 10.5220/0003369004370441