1

我正在尝试实现 Evgeny Kluev 在他对循环滚动算法的回答中给出的算法 ，但我无法让它工作。以下是我尝试按照他的指示手工制作的示例：

text: ababacababd


<STEP 1>                                    
  suffixes and LCPs:                               

  ababacababd                                            
  4 
  ababd 
  3 
  abacababd 
  2  
  abd
  1
  acababd
  0
  babacababd
  3
  babd
  2
  bacababd
  1
  bd
  0
  cababd
  0
  d

<STEP 2>
  sorted LCP array indices: 0,1,5,2,6,3,7,4,8,9
                 (values) : 4,3,3,2,2,1,1,1,0,0

<STEP 3>
LCP groups sorted by position in text (format => position: entry):
  lcp 4:
    0: ababacababd
    6: ababd

  lcp 3:
    1: babacababd
    2: abacababd
    6: ababd
    7: babd

  lcp 2:
    2: abacababd
    3: bacababd
    7: babd
    8: abd

  lcp 1:
    3: bacababd
    4: acababd
    8: abd
    9: bd

  lcp 0:
    0: ababacababd
    1: babacababd
    4: acababd
    5: cababd
    9: bd
   10: d

<STEP 4>
entries remaining after filter (LCP == positional difference):
   none! only (abd),(bd) and (bacababd),(acababd) from LCP 1 group
   have positional difference equal to 1 but they don't share prefixes
   with each other. shouldn't i have at least (ab) and (ba) here?

谁能告诉我在这个过程中我做错了什么？

此外，他说在第 4 步结束时我们应该在文本中包含所有可能的序列，他的意思是所有可能的重复序列吗？

这是一个已知算法，我可以在其他地方找到更多详细信息吗？

（我也对他在第 5 步中对相交序列的定义感到困惑，但如果我正确理解了前面的步骤，也许会有意义）。

编辑：这是我在 Evgeny 的有用澄清后的第 4、5、6 步：

<STEP 4>
filter pseudocode:
results = {}
for (positions,lcp) in lcp_groups:
  results[lcp] = []
  while positions not empty:
    pos = positions.pop(0) #pop lowest element
    if (pos+lcp) in positions:
      common = prefix(input, pos, lcp)
      if common.size() < lcp:
        next
      i = 1
      while (pos+lcp*(i+1)) in positions:
        if common != prefix(input, pos+lcp*i, lcp):
          break
        positions.delete(pos+lcp*i)
        i += 1

      results[lcp].append( (common, pos, i+1) )

application of filter logic:
  lcp 4:
    0: ababacababd # 4 not in {6}
    6: ababd       # 10 not in {}

  lcp 3:
    0: ababacababd # 3 not in {1,2,6,7}
    1: babacababd  # 4 not in {2,6,7}
    2: abacababd   # 5 not in {6,7}
    6: ababd       # 9 not in {7}
    7: babd        # 10 not in {}

  lcp 2:
    0: ababacababd # 2 in {1,2,3,6,7,8}, 4 not in {1,2,3,6,7,8} => ("ab", 0, 2)
    1: babacababd  # 3 in {2,3,6,7,8}, 5 not in {2,3,6,7,8} => ("ba", 1, 2)
    2: abacababd   # 4 not in {3,6,7,8}
    3: bacababd    # 5 not in {6,7,8}
    6: ababd       # 8 in {7,8}, 10 not in {7,8} => ("ab", 6, 2)
    7: babd        # 9 not in {8}
    8: abd         # 10 not in {}

  lcp 1:
    0: ababacababd # 1 in {1,2,3,4,6,7,8,9}, prefix is ""
    1: babacababd  # 2 in {2,3,4,6,7,8,9}, prefix is ""
    2: abacababd   # 3 in {3,4,6,7,8,9}, prefix is ""
    3: bacababd    # 4 in {4,6,7,8,9}, prefix is ""
    4: acababd     # 5 not in {6,7,8,9}
    6: ababd       # 7 in {7,8,9}, prefix is ""
    7: babd        # 8 in {8,9}, prefix is ""
    8: abd         # 9 in {9}, prefix is ""
    9: bd          # 10 not in {}

sequences: [("ab", 0, 2), ("ba", 1, 2), ("ab", 6, 2)]

<STEP 5>
add sequences in order of LCP grouping. sequences within an LCP group
are added according to which was generated first:
  lcp 4: no sequences
  lcp 3: no sequences
  lcp 2: add ("ab", 0, 2)
  lcp 2: dont add ("ba", 1, 2) because it intersects with ("ab", 0, 2)
  lcp 2: add ("ab", 6, 2)
  lcp 1: no sequences

collection = [("ab", 0, 2), ("ab", 6, 2)]
(order by position not by which one was added first)

<STEP 6>
recreate input by iterating through the collection in order and 
filling in gaps with the normal input:
  input = "ab"*2 + input[4..5] + "ab"*2 + input[10..10]

Evgeny，如果你碰巧再次看到这个问题，给你一个快速的问题：我是否正确执行了第 5 步？也就是说，我是否根据它们生成的 LCP 组添加序列（首先具有更高 LCP 值的组）？还是与LCP有关的其他东西？

另外，如果第 4 步或第 6 步有任何问题，请告诉我，但似乎我所拥有的对于这个示例非常有效。

4

1 回答 1

1

我必须澄清原始答案中“按 LCP 值分组”的含义。事实上，对于具有选定 LCP 值的组，我们应该包括所有具有较大 LCP 值的条目。

这意味着对于您的示例，在处理 LCP3 时，我们需要将前面的条目 0 和 6 合并到该组。在处理 LCP2 时，我们需要将所有前面的条目与 LCP3 和 LCP4 合并：0、1、2、6、7。

结果，过滤后剩下两对（ab）对以及一对（ba）对。但由于 (ba) 与第一个 (ab) 对“相交”，因此在第 5 步被拒绝。

此外，他说在第 4 步结束时我们应该在文本中包含所有可能的序列，他的意思是所有可能的重复序列吗？

没错，我的意思是所有可能的重复序列。

这是一个已知算法，我可以在其他地方找到更多详细信息吗？

我不知道。以前从未见过这样的算法。

以下是步骤 2 .. 4 的实现方式（以伪代码形式）：

for (in_sa, in_src) in suffix_array: # step 2
  lcp_groups[max(LCP[in_sa.left], LCP[in_sa.right])].append((in_sa, in_src))
apply(sort_by_position_in_src, lcp_groups) # step 3
for lcp from largest downto 1: # step 4
  # sorted by position in src array and unique:
  positions = merge_and_uniq(positions, lcp_groups[lcp])
  for start in positions:
    pos = start
    while (next = positions[pos.in_src + lcp]).exists
           and LCP.RMQ(pos.in_sa, next.in_sa) >= lcp
           and not(prev = positions[pos.in_src - lcp]).exists  # to process each
                   and LCP.RMQ(pos.in_sa, prev.in_sa) >= lcp): # chain only once
      pos = next
    if pos != start:
      pass_to_step5(start, lcp, pos + lcp)

在这里，我没有为positions. 但是为了方便起见，假设了一个有序的关联数组。RMQ 是 Range Minimum Query，因此应该对 LCP 数组进行相应的预处理。

此代码实际上与 OP 中的代码相同。common != prefix(input, pos+lcp*i, lcp)但它使用 RMQ代替昂贵的字符串比较（如带有前面的子字符串）。

它具有二次最坏情况时间复杂度。对于像“aaaaaaaaa”这样的输入数组应该很慢。而且要找到“更好”字符串的时间复杂度并不容易，在“平均”情况下它可能是次二次的。同样的问题可以用更简单的二次时间算法来解决：

def loop_rolling(begin, end):
  distance = (end - begin) / 2)
  for d from distance downto 1:
    start = pos = begin
    while pos + d < end:
      while (pos + d < end) and (src[pos] == src[pos + d]):
        ++pos
      repeats = floor((pos - start) / d)
      if repeats > 0:
        pass_to_step5(start, d, start + d * (repeats + 1))
      start = pos

或者可以通过删除步骤 5 和 6 使其更简单。但下面的变体有一个缺点。它太贪心了，所以它会找到 2*(2*(ab))ab 而不是 5*(ab)：

def loop_rolling(begin, end, distance):
  distance = min(distance, (end - begin) / 2))
  for d from distance downto 1:
    start = pos = begin
    while pos + d < end:
      while (pos + d < end) and (src[pos] == src[pos + d]):
        ++pos
      repeats = floor((pos - start) / d)
      if repeats > 0:
        loop_rolling(begin, start, d - 1)
        print repeats+1, "*("
        loop_rolling(start, start + d, d - 1) # "nested loops"
        print ')'
        loop_rolling(start + d * (repeats + 1), end, d)
        return
      else:
        if d == 1: print src[start .. pos]
        start = pos
于 2013-10-14T12:36:26.337 回答