On Bit-Parallel Processing of Multi-byte Text
On Bit-Parallel Processing of Multi-byte Text
复制标题
多字节文本的位并行处理
DOI：
10.1007/978-3-540-31871-2_25
复制
发表时间：
2004
期刊：
影响因子：
--
通讯作者：
M. Takeda
中科院分区：
文献类型：
--
作者：
Heikki Hyyrö;Jun Takaba;A. Shinohara;M. Takeda
对于几种类型的成对字符串处理，例如最长公共子序列计算或近似字符串匹配，存在实用的位并行算法。位并行算法通常使用匹配位向量的大小-σ表，其中字符λ的向量中的位标识字符λ在处理的字符串之一中出现的位置，并且σ是字母表大小。计算匹配表的时间或空间成本对于诸如ASCII文本之类的相当小的字母表来说并不令人望而却步。然而，例如在一般Unicode文本的情况下，字符的可能的数字代码范围大约是一百万。这使得使用简单的表不切实际。在本文中，我们评估三种不同的方案来克服这个问题。首先，我们建议用字符代码自动机代替字符代码表。然后，我们将此方法与其他两种方案进行比较：使用哈希表，以及Wu，Manber和Myers提出的基于二进制搜索的解决方案[25]。我们发现最好的选择是使用基于自动机的方法或哈希表。
There exist practical bit-parallel algorithms for several types of pair-wise string processing, such as longest common subsequence computation or approximate string matching. The bit-parallel algorithms typically use a size-σtable of match bit-vectors, where the bits in the vector for a characterλidentify the positions where the characterλoccurs in one of the processed strings, andσis the alphabet size. The time or space cost of computing the match table is not prohibitive with reasonably small alphabets such as ASCII text. However, for example in the case of general Unicode text the possible numerical code range of the characters is roughly one million. This makes using a simple table impractical. In this paper we evaluate three different schemes for overcoming this problem. First we propose to replace the character code table by a character code automaton. Then we compare this method with two other schemes: using a hash table, and the binary-search based solution proposed by Wu, Manber and Myers [25]. We find that the best choice is to use either the automaton-based method or a hash table.
Masayuki Takeda、Satoru Miyamoto、Takuya Kida、Ayumi Shinohara、Shuichi Fukamachi、Takeshi Shinohara、Setsuo Arikawa：“按原样处理文本文件：压缩文本、多字节字符文本和半结构化文本的模式匹配”讲义
DOI：
--
发表时间：
--
期刊：
影响因子：
--
作者：
通讯作者：
--