The practicality of text signatures for accelerating string searching
作者:
Alan L. Tharp,
Kuo‐Chung Tai,
期刊:
Software: Practice and Experience
(WILEY Available online 1982)
卷期:
Volume 12,
issue 1
页码: 35-44
ISSN:0038-0644
年代: 1982
DOI:10.1002/spe.4380120104
出版商: John Wiley&Sons, Ltd.
关键词: String searching;Pattern matching;Text signatures;Hashing
数据来源: WILEY
摘要:
AbstractThis paper studies the use of text signatures in string searching. Text signatures are a coded representation of a unit of text formed by hashing substrings into bit positions which are, in turn, set to one. Then instead of searching an entire line of text exhaustively, the text signature may be examined first to determine if complete processing is warranted. A hashing function which minimizes the number of collisions in a signature is described. Experimental results for two signature lengths with both a text file and a program file are given. Analyses of the results and the utility and application of the method conclude the discussion.
点击下载:
PDF
(579KB)
返 回