• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>電子情報通信学会技術研究報告 >非線形テキストにおける最長共通部分文字列・部分列アルゴリズム
【24h】

非線形テキストにおける最長共通部分文字列・部分列アルゴリズム

机译：非线性文本中最长的公共子字符串/子字符串算法

获取原文
获取原文并翻译 | 示例
           
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

A non-linear text is a directed graph where each vertex is labeled with a string. In this paper, we define Longest common substring/subsequence problems on Non-linear texts and solve them, to measure degree of similarity between two non-linear texts.We propose O（∣E_1∣∣E_2∣)-time algorithms on acyclic non-linear texts, where |E_1|,|E_2| are the numbers of edges in the non-linear texts G_1,G_2- In addition we propose an O (| E_1 | +1 |E_2 | +1 |E'_1||E‘_2| +1|V'_1||V'_2| log | ∑ | +|∑| log |∑|)-time algorithm to solve a longest common subsequence problem on cyclic non-linear texts, where |E'_1|, |E'_2|,|V'_1|,|V'_2| are the numbers of edges and vertexes in the non-linear texts which are transformed from G_1,G_2.%非線形テキストは，文字列を頂点ラベルとする有向グラフである．本論文では，二つの非線形テキストに対して，その類似性を調べる為に，二つの非線形テキストにおける最長共通部分文字列問題と最長共通部分列問題を定義し，サイクルを含まない非線形テキストに対し，O（∣E_1∣∣E_2∣）時間での解法を提案する．ここで，∣E_1∣,∣E_2∣は二つの非線形テキストG_1，G_2のそれぞれの辺の数を表す．また，サイクルを含む非線形テキストにおける最長共通部分列問題のO(∣E_1∣+∣E_2∣+∣E'_1∣∣E'_2∣＋∣V'_1∣∣V'_2∣ log ∣∑∣＋∣∑∣log ∣∑∣）時間での解法を提案する．ここで，∣∑∣はアルファベットサイズE'_1，E'_2，V'_1，V'_2はそれぞれG_1，G_2をサイクルを一つの頂点と見なし，変形した後の辺の数と頂点数を表す．
机译：非线性文本是有向图，其中每个顶点都用字符串标记。在本文中，我们定义了非线性文本上的最长公共子字符串/子序列问题并将其求解，以测量两个非线性文本之间的相似度我们针对非循环非线性文本提出O（∣E_1∣∣E_2∣）时间算法，其中| E_1 |，| E_2 |是非线性文本G_1，G_2中的边数。此外，我们提出了O（| E_1 | +1 | E_2 | +1 | E'_1 || E'_2 | +1 | V'_1 || V'_2 | log | ∑ | + | ∑ | log | ∑ |）-时间算法解决循环非线性文本上的最长公共子序列问题，其中| E'_1 |，| E'_2 |，| V'_1 |，| V'_2 |是非线性中边和顶点的数目从G_1，G_2。％转换而来的文本。非线性文本是有向图，其中字符串是顶点标签。在本文中，我们定义了两个非线性文本中最长的公共子串问题和最长的公共子序列问题，以研究它们之间的相似性。我们提出了O（∣E_1∣∣E_2∣）时间的解决方案。在此，∣E_1∣和∣E_2∣表示两个非线性文本G_1和G_2中的每一个的边数。另外，包含周期的非线性文本中最长公共子序列问题的O（∣E_1∣ + ∣E_2∣ + ∣E'_1∣∣E'_2∣ ＋ ∣V'_1∣∣V'_2∣log ＋ ＋ ∣log∣log∣∑∣）我们提出了一种及时的解决方法。其中∣∑∣是字母大小E'_1，E'_2，V'_1和V'_2将G_1和G_2视为一个顶点，并表示变形后的边数和顶点数。 。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号