The Suffix of a square matrix, with applications
The Suffix of a square matrix, with applications
复制标题
方阵的后缀及其应用
DOI：
--
复制
发表时间：
1993
期刊：
影响因子：
--
通讯作者：
R. Giancarlo
中科院分区：
文献类型：
--
作者：
R. Giancarlo
我们描述一种新的数据结构，Lst@ix树，它是对麦克雷特针对有序字母表字符串的后缀树在方阵上的一种推广。所有矩阵的元素都在一个全序集中。基于L后缀树，我们针对在低级图像处理[19]和视觉数据库[18]的许多重要应用中出现的以下问题的静态和动态版本给出了高效算法：
二维模式检索：我们有一个文本库S = {TEXT1，…，TEXTr}，其中TEXTi是一个ni×ni矩阵，1 < i < r。在静态版本中，我们可以对该库进行预处理。给定一个m×m的模式矩阵PAT，我们希望找到PAT在所有TEXT∈S中的所有出现位置（查询）。在动态版本中，我们可以通过向库S中插入或从其中删除一些TEXT来更新它。查询与静态版本相同，但与更新操作混合在一起。
二维字典匹配：我们有一个模式字典DC = {PAT1，…，PATs}，其中PATi的维度是mi×mi，1 < i < s。在静态情况下，我们可以对字典进行预处理。给定一个n×n的文本矩阵TEXT，我们希望在文本中搜索字典中模式的所有出现位置（搜索步骤）。在动态版本中，我们可以通过向其中插入或删除一些矩阵（模式）来更新DC。
We describe a new data structure, the Lst@ix tree, which is a generalization to a souare matrix of McCreieht’s suffix tree ‘ior a string ordered alohabet . All-matrices have entries ii a totally . Based on the Lsuffix tree. we eive efficient algorithms for the static and dynamic ver&ns of the following problems that arise in many important applications in low-level image processing [19] and in visual databases [1S]: Two-Dimensional Pattern Retrieval: We have a library of texts S = {TEXT’, . . . ,TEXT’}, where TEXT’ is an ni x ni matrix, 1 < i < r. In the static version, we may preprocess the.libr&y. -Given an m x m pattern matrix PAT, we want to find all occurrences of PAT in TEXT (query), for all TEXT E S. In th e d ynamic version, we can update the librarv S bv insertine in it or deletine from it some TEXT. The query is as i; the static versi& but is intermixed with update operations. Two-Dimensional Dictionary Matching: We have a dictionary of patterns DC = {PAZ, ... , PAT,}, where PAZ is of dimension mi x mi, 1 < i < s. In the static case, we may preprocess the dictionary. liven an n x n text matrix TEXT, we want to search for all occurrences of patterns in the dictionary in the text (search step). In the dynamic version, we can update DC by inserting or deleting some matrix (pattern) from it.