Online Pattern Matching for String Edit Distance with Moves
Online Pattern Matching for String Edit Distance with Moves
复制标题
字符串编辑距离与移动的在线模式匹配
DOI：
10.1007/978-3-319-11918-2_20
复制
发表时间：
2014
期刊：
影响因子：
--
通讯作者：
Hiroshi Sakamoto
中科院分区：
文献类型：
--
作者：
Yoshimasa Takabatake;Yasuo Tabei;Hiroshi Sakamoto
带移动的编辑距离（EDM）是一种字符串到字符串的距离度量，除了将一个字符串转换为另一个字符串的顺序编辑操作之外，还包括子字符串移动。虽然优化EDM是棘手的，它有许多应用，特别是在错误检测。ESP是一种有效的语法分析算法，它保证了同一个子串在不同的外观之间的语法差异有一个上界。ESP可以用来计算一个近似的EDM作为L1距离的特征向量之间建立的节点标签在分析树。然而，ESP不适用于其中整个文本事先未知的流文本数据。我们提出了一个在线ESP（OESP），使EDM的在线模式匹配。OESP为流媒体文本构建解析树，在线计算特征向量间的L1距离。对于EDM的空间有效的计算，OESP直接编码的解析树到一个简洁的表示，通过利用动态简洁树的最新结果背后的想法。我们实验测试OESP的能力，以在线方式计算EDM基准数据集上，我们显示OESP的效率。
Edit distance with moves (EDM) is a string-to-string distance measure that includes substring moves in addition to ordinal editing operations to turn one string to the other. Although optimizing EDM is intractable, it has many applications especially in error detections. Edit sensitive parsing (ESP) is an efficient parsing algorithm that guarantees an upper bound of parsing discrepancies between different appearances of the same substrings in a string. ESP can be used for computing an approximate EDM as theL1distance between characteristic vectors built by node labels in parsing trees. However, ESP is not applicable to a streaming text data where a whole text is unknown in advance. We present an online ESP (OESP) that enables an online pattern matching for EDM. OESP builds a parse tree for a streaming text and computes theL1distance between characteristic vectors in an online manner. For the space-efficient computation of EDM, OESP directly encodes the parse tree into a succinct representation by leveraging the idea behind recent results of a dynamic succinct tree. We experimentally test OESP on the ability to compute EDM in an online manner on benchmark datasets, and we show OESP’s efficiency.