3

我最近编写了一些处理字符串的 Scala 代码，找到它的所有子字符串并保留在字典中找到的那些的列表。整个字符串中子字符串的开头和结尾也必须保留以供以后使用，因此最简单的方法似乎就是使用嵌套的 for 循环，如下所示：

for (i <- 0 until word.length)
  for (j <- i until word.length) {
    val sub = word.substring(i, j + 1)
    // lookup sub in dictionary here and add new match if found
  }

作为练习，我决定尝试在 Haskell 中做同样的事情。它看起来很简单，不需要子字符串索引 - 我可以使用类似这种方法来获取子字符串，然后调用递归函数来累积匹配项。但如果我也想要索引，它似乎更棘手。

我将如何编写一个函数，该函数返回一个列表，该列表包含每个连续的子字符串及其在“父”字符串中的开始和结束索引？

例如tokens "blah"会给[("b",0,0), ("bl",0,1), ("bla",0,2), ...]

更新

精选的答案和大量新事物可供探索。在搞砸了一点之后，我已经去了第一个答案，丹尼尔的建议是允许使用[0..].

data Token = Token String Int Int 

continuousSubSeqs = filter (not . null) . concatMap tails . inits

tokenize xs = map (\(s, l) -> Token s (head l) (last l)) $ zip s ind
    where s = continuousSubSeqs xs
          ind = continuousSubSeqs [0..]

鉴于我有限的 Haskell 知识，这似乎相对容易理解。

4

4 回答 4

2 
import Data.List

continuousSubSeqs = filter (not . null) . concatMap inits . tails

tokens xs = map (\(s, l) -> (s, head l, last l)) $ zip s ind
    where s   = continuousSubSeqs xs
          ind = continuousSubSeqs [0..length(xs)-1]

像这样工作：

tokens "blah"
[("b",0,0),("bl",0,1),("bla",0,2),("blah",0,3),("l",1,1),("la",1,2),("lah",1,3),("a",2,2),("ah",2,3),("h",3,3)]
于 2012-07-15T22:05:06.773 回答
1

我的版本：

import Data.List

tokens = 
  map join . filter (not . null) . concatMap inits . tails . zip [0..]
  where 
    join s@((i, _):t) = 
      (map snd s, i, foldl' (\_ i -> i) i (map fst t))

main =
  putStrLn $ show $ tokens "blah"

-- [("b",0,0),("bl",0,1),("bla",0,2),("blah",0,3),("l",1,1),("la",1,2),("lah",1,3),("a",2,2),("ah",2,3),("h",3,3)]

更新：

import Control.Arrow

...

tokens = 
  map join . filter (not . null) . concatMap inits . tails . zip [0..] where 
    join s = (s', i, j) where 
      ((i, j), s') = (first (head &&& last)) $ unzip s

...
于 2012-07-16T00:14:32.963 回答
1

您编写的两个嵌套循环是一个很好的起点。也就是说，我们可以编写一个函数tokens，将其工作委托给两个递归函数outer并inner对应于您的循环：

type Token a = ([a], Int, Int)

tokens :: [a] -> [Token a]
tokens = outer 0
  where
    outer _ []         = []
    outer i l@(_ : xs) = inner i [] l ++ outer (i + 1) xs
      where
        inner _ _ []         = []
        inner j acc (x : xs) =
          (acc ++ [x], i, j) : inner (j + 1) (acc ++ [x]) xs

在这里，outer遍历字符串，并且对于该字符串中的每个起始位置，调用inner以收集从该位置开始的所有段及其结束位置。

虽然这个功能满足你的要求，

> tokens "blah"
[("b",0,0),("bl",0,1),("bla",0,2),("blah",0,3),("l",1,1),("la",1,2),("lah",1,3),("a",2,2),("ah",2,3),("h",3,3)]

由于重复的列表连接，它非常低效。更有效的版本会将其结果累积在所谓的差异列表中：

type Token a = ([a], Int, Int)

tokens :: [a] -> [Token a]
tokens l = outer 0 l []
  where
    outer _ []         = id
    outer i l@(_ : xs) = inner i id l . outer (i + 1) xs
      where
        inner _ _ []         = id
        inner j acc (x : xs) =
          ((acc [x], i, j) :) . inner (j + 1) (acc . (x :)) xs

当然，如何构建字典取决于您选择如何表示它。这是一种使用简单有序关联列表的方法，

type Dict a = [([a], [(Int, Int)])]

empty :: Dict a
empty = []

update :: Ord a => Token a -> Dict a -> Dict a
update (xs, i, j) []                = [(xs, [(i, j)])]
update (xs, i, j) ((ys, ns) : dict) = case compare xs ys of
  LT -> (xs, [(i, j)]) : (ys, ns) : dict
  EQ -> (ys, (i, j) : ns) : dict
  GT -> (ys, ns) : update (xs, i, j) dict

toDict :: Ord a => [a] -> Dict a
toDict = foldr update empty . tokens

但是由于您的键是字符串，因此尝试（又名前缀树）可能是更好的选择。

如果您追求的是有效的子字符串查询，我建议您查看suffix trees，尽管它们的实现有些涉及。您可能想查看

  • 罗伯特·吉格里奇和斯特凡·库尔茨。命令式和纯函数式后缀树结构的比较。计算机编程科学25(2–3):187–218, 1995

和 Bryan O'Sullivan 关于 Hackage 的suffixtree包。

于 2012-07-16T07:00:15.700 回答
1

另一个版本更容易从左到右阅读，类似于 unix 管道

import Data.List
import Control.Category 

tokens = 
     tailsWithIndex
     >>> concatMap (\(i,str) -> zip (repeat i) (initsWithIndex str))
     >>> map adjust
     where
       tailsWithIndex = tails >>> init >>> zip [0..]
       initsWithIndex = inits >>> tail >>> zip [0..]
       adjust (i, (j, str)) = (str, i, i+j)

样品运行

>tokens "blah" 
[("b",0,0),("bl",0,1),("bla",0,2),("blah",0,3),("l",1,1),("la",1,2),("lah",1,3),("a",2,2),("ah",2,3),("h",3,3)]

如果concatMap是惰性的，那么整个计算都是惰性的并且将是高效的，除了使用 Data.List 函数而不是原始列表访问。

于 2012-07-16T09:22:22.260 回答