模块化行程编码

Question

题

如何实现运行长度编码模数n>=1？因为n=4，考虑到输入AAABBBBABCCCCBBBDAAA，我们想要一个输出[('D', 1), ('A', 3)]。注意由于模数运算导致的长距离合并。见说明。

解释

中第一次出现BBBB编码到(B, 4)其modulus 4是(B, 0)，从而消除本身进行。参见图表（忽略空格；它们仅用于说明目的）：

AAABBBBABCCCCBBBDAAA
A3  B4 ABCCCCBBBDAAA
A3  B0 ABCCCCBBBDAAA
A3     ABCCCCBBBDAAA
A4      BCCCCBBBDAAA
A0      BCCCCBBBDAAA
        BCCCCBBBDAAA
        ... 
                DA3

一个更简单的例子，当没有合并发生时，因为没有被取消modulus 4：输入AAABABBBC产生输出[('A',3),('B',1),('A',1),('B',3),('C',1)]。

要求

• Haskell 实现是首选，但也欢迎其他实现！
• 比 3rd 方库更喜欢标准/公共库函数。
• 首选使用高阶函数的可读和简洁的程序。
• 优先考虑效率（在不必要时不要遍历整个列表）

我的程序

我在 Haskell 中实现了这个，但它看起来太冗长而且读起来很糟糕。关键思想是一次检查三个元组，如果我们既不能取消0元组也不能在手头的三个元组中合并一对元组，则只向前推进一个元组。

import Data.List (group)

test = [('A', 1), ('A', 2), ('B', 2), ('B', 2), ('A', 1), ('B', 1), ('C', 1), ('C', 3), ('B', 3), ('D', 1), ('A', 3)] :: [(Char, Int)]
expected = [('D', 1), ('A', 3)] :: [(Char, Int)]


reduce' :: [(Char, Int)] -> [(Char, Int)]
reduce' [           ] = []                                           -- exit
reduce' (   (_,0):xs) = reduce' xs
reduce' (x1:(_,0):xs) = reduce' (x1:xs)
reduce' (   (x,n):[]) = (x,n):[]                                     -- exit

reduce' (        (x1,n1):(x2,n2):[])              -- [previous,current,NONE]
  | x1 == x2  = reduce' ((x1, d4 (n1+n2)):[])
  | otherwise = (x1,n1):(                                         -- advance
                reduce' ((x2, d4     n2 ):[]))

reduce' ((x1,n1):(x2,n2):(x3,n3):xs)              -- [previous,current,next]
  | n3 == 0   = reduce' ((x1, d4  n1    ):(x2, d4  n2    ):xs)
  | n2 == 0   = reduce' ((x1, d4  n1    ):(x3, d4     n3 ):xs)
  | x2 == x3  = reduce' ((x1, d4  n1    ):(x2, d4 (n2+n3)):xs)
  | x1 == x2  = reduce' ((x2, d4 (n1+n2)):(x3, d4     n3 ):xs)
  | otherwise = (x1,n1):(                                         -- advance
                reduce' ((x2, d4  n2    ):(x3, d4     n3 ):xs)
                )

-- Helpers
flatten :: [(Char, Int)] -> String
flatten nested = concat $ (\(x, n) -> replicate n x) <$> nested

nest :: String -> [(Char, Int)]
nest flat = zip (head <$> xg) (d4 .length <$> xg)
  where xg = group flat

reduce = reduce' . nest
d4 = (`rem` 4)

想法

我的输入就像test上面剪辑中的变量。我们可以继续做flatten，然后nest到它的结果不会改变，肯定会看简单。但是感觉它是多次扫描整个列表，而我的 3 指针实现只扫描整个列表一次。也许我们可以从左侧弹出一个元素并将其添加到新堆栈中，同时合并相同的连续项目？或者也许使用 Applicative Functors？例如，这工作，但不知道它的效率/性能：reduce = (until =<< ((==) =<<)) (nest . flatten)。

Answer 1

算法

我认为你完全从字符串的角度考虑这个问题会使这个问题变得更加困难。相反，做一个只做无聊的 RLE 部分的初步通过。这样，第二遍相对容易，因为您可以使用代表特定长度运行的“令牌”，而不必一次处理一个字符。

我们在第二次遍历列表时需要维护的唯一数据结构是一个堆栈，我们只需要查看它的顶部元素。我们将我们正在检查的每个令牌与堆栈顶部进行比较。如果它们相同，我们将它们混合成一个表示它们串联的标记；否则，我们只需将下一个令牌压入堆栈。在任何一种情况下，我们都会减少令牌大小 mod N 并删除大小为 0 的令牌。

表现

• 该算法在线性时间内运行：它只处理每个输入令牌一次，并为每个令牌执行恒定量的工作。
• 它不能懒惰地产生输出。没有输入的前缀足以自信地产生输出的前缀，因此我们必须等到我们消耗了整个输入才能产生任何输出。如果字符串的其余部分是CCCBBBAAA....
• 最后的反向是一个无赖，但在所有代币上摊销它非常便宜，并且在任何情况下都不会恶化我们的线性时间保证。它同样不会改变我们的空间要求，因为我们已经需要 O(N) 空间来缓冲输出（因为正如前面的说明所说，永远不可能发出部分结果）。

正确性

写下我关于懒惰的评论让我想到了你的reduce解决方案，它似乎懒惰地产生输出，我认为这是不可能的。事实证明，解释是您的实现不仅不优雅，如您所说，而且不正确。它过早地产生输出，错过了用后面的元素取消的机会。我能发现你失败的最简单的测试用例是reduce "ABABBBBAAABBBAAA" == [('A',1),('A',3)]. 我们可以证实，这是由于产生的结果还为时过早，时指出，take 1 $ reduce ("ABAB" ++ undefined)收益率[(1, 'A')]即使元素可能晚一点以该第一A.取消

细节

最后请注意，我使用自定义数据类型Run只是为了给这个概念命名；当然，您可以廉价地将其转换为元组，或者如果您愿意，可以重写该函数以在内部使用元组。

执行

import Data.List (group)

data Run a = Run Int a deriving Show

modularRLE :: Eq a => Int -> [a] -> [Run a]
modularRLE groupSize = go [] . tokenize
  where go stack [] = reverse stack
        go stack (Run n x : remainder) = case stack of
          [] -> go (blend n []) remainder
          (Run m y : prev) | x == y -> go (blend (n + m) prev) remainder
                           | otherwise -> go (blend n stack) remainder
          where blend i s = case i `mod` groupSize of
                              0 -> s
                              j -> Run j x : s
        tokenize xs = [Run (length run) x | run@(x:_) <- group xs]
?> modularRLE 4 "AAABBBBABCCCCBBBDAAA"
[Run 1 'D',Run 3 'A']
?> modularRLE 4 "ABABBBBAAABBBAAA"
[]