- html - 出于某种原因,IE8 对我的 Sass 文件中继承的 html5 CSS 不友好?
- JMeter 在响应断言中使用 span 标签的问题
- html - 在 :hover and :active? 上具有不同效果的 CSS 动画
- html - 相对于居中的 html 内容固定的 CSS 重复背景?
我正在使用以下数据类型:
data SuffixTree = Leaf Int | Node [(String, SuffixTree)]
deriving (Eq, Show)
每个子树都有一个对应的标签(字符串)。想法是通过将每个后缀及其索引添加到累积树中来构建相应的后缀树(开头是Node []
)。
这已经定义了
buildTree s
= foldl (flip insert) (Node []) (zip (suffixes s) [0..length s-1])
suffixes
的定义正确。
我一直在尝试实现 insert
函数一段时间,但似乎无法成功。
这是我现在拥有的(名称和样式不是最好的,因为这仍在进行中):
insert :: (String, Int) -> SuffixTree -> SuffixTree
insert pair tree@(Node content)
= insert' pair tree content
where
insert' :: (String, Int) -> SuffixTree -> [(String, SuffixTree)] -> SuffixTree
insert' (s, n) (Node []) subtrees
= Node ((s, Leaf n) : subtrees)
insert' (s, n) (Node content@((a, tree) : pairs)) subtrees
| null p = insert' (s, n) (Node pairs) subtrees
| p == a = insert' (r, n) tree subtrees
| p /= a = Node ((p, newNode) : (subtrees \\ [(a, tree)]))
where
(p, r, r') = partition s a
newNode = Node [(r, (Leaf n)), (r', tree)]
partition
函数接受两个字符串并返回一个元组,包括:
我想我了解构建树所需的规则。
我们首先将第一个子树的标签与我们要插入的字符串(例如,str
)进行比较。如果它们没有共同的前缀,我们会尝试在下一个子树中插入。
如果标签是 str
的前缀,我们继续查看该子树,但我们尝试插入 str
而不是使用 str
> 没有前缀。
如果 str
是 label 的前缀,那么我们用一个新的 Node
替换现有的子树,有一个 Leaf
和旧的子树.我们还调整了标签。
如果我们在 str
和任何标签之间没有匹配,那么我们将一个新的 Leaf
添加到子树列表中。
但是,我遇到的最大问题是我需要返回包含更改的新树,因此我必须跟踪树中的其他所有内容(不知道如何执行此操作,或者我的想法是否正确关于这个)。
代码似乎在此字符串上正常工作:"banana"
:
Node [("a",Node [("",Leaf 5),("na",Node [("",Leaf 3),("na",Leaf 1)])]),
("na",Node [("",Leaf 4),("na",Leaf 2)]),("banana",Leaf 0)]
然而,在这个字符串 "mississippi"
我得到一个 Exception: Non-exhaustive patterns in function insert'
。
非常感谢任何帮助或想法!
最佳答案
您正在使用 二次 算法;而最佳情况下,后缀树可以在线性时间内构建。也就是说,坚持使用相同的算法,可能更好的方法是首先构建(未压缩的)suffix trie(不是树),然后压缩生成的 trie。
优点是可以使用 Data.Map
来表示后缀树:
data SuffixTrie
= Leaf' Int
| Node' (Map (Maybe Char) SuffixTrie)
这使得操作比对列表更有效和更容易。这样做,您还可以完全绕过常见的前缀计算,因为它会自行产生:
import Data.List (tails)
import Data.Maybe (maybeToList)
import Control.Arrow (first, second)
import Data.Map.Strict (Map, empty, insert, insertWith, assocs)
data SuffixTree
= Leaf Int
| Node [(String, SuffixTree)]
deriving Show
data SuffixTrie
= Leaf' Int
| Node' (Map (Maybe Char) SuffixTrie)
buildTrie :: String -> SuffixTrie
buildTrie s = foldl go (flip const) (init $ tails s) (length s) $ Node' empty
where
go run xs i (Node' ns) = run (i - 1) $ Node' tr
where tr = foldr loop (insert Nothing $ Leaf' (i - 1)) xs ns
loop x run = insertWith (+:) (Just x) . Node' $ run empty
where _ +: Node' ns = Node' $ run ns
buildTree :: String -> SuffixTree
buildTree = loop . buildTrie
where
loop (Leaf' i) = Leaf i
loop (Node' m) = Node $ con . second loop <$> assocs m
con (Just x, Node [(xs, tr)]) = (x:xs, tr) -- compress single-child nodes
con n = maybeToList `first` n
然后:
\> buildTree "banana"
Node [("a",Node [("",Leaf 5),
("na",Node [("",Leaf 3),
("na",Leaf 1)])]),
("banana",Leaf 0),
("na",Node [("",Leaf 4),
("na",Leaf 2)])]
类似:
\> buildTree "mississippi"
Node [("i",Node [("",Leaf 10),
("ppi",Leaf 7),
("ssi",Node [("ppi",Leaf 4),
("ssippi",Leaf 1)])]),
("mississippi",Leaf 0),
("p",Node [("i",Leaf 9),
("pi",Leaf 8)]),
("s",Node [("i",Node [("ppi",Leaf 6),
("ssippi",Leaf 3)]),
("si",Node [("ppi",Leaf 5),
("ssippi",Leaf 2)])])]
关于string - 通过在 Haskell 中插入每个后缀来构建后缀树,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/41333083/
如果您想使用 String.Concat() 连接 5 个或更多字符串,则它会使用 Concat(String[])。 为什么不一直使用 Concat(String[]) 而不再需要 Concat(S
今天在使用 String 时,我遇到了一种我以前不知道的行为。我无法理解内部发生的事情。 public String returnVal(){ return "5";
似乎在我所看到的任何地方,都有一些过时的版本,这些版本不再起作用。 我的问题似乎很简单。我有一个Java类,它映射到derby数据库。我正在使用注释,并且已经成功地在数据库中创建了所有其他表,但是在这
一、string::size_type() 在C++标准库类型 string ,在调用size函数求解string 对象时,返回值为size_type类型,一种类似于unsigned类型的int 数据
我正在尝试将数据保存到我的 plist 文件中,其中包含字符串数组的定义。我的plist - enter image description here 我将数据写入 plist 的代码是 -- let
我有一个带有键/值对的 JavaScript 对象,其中值是字符串数组: var errors = { "Message": ["Error #1", "Error #2"], "Em
例如,为了使用相同的函数迭代 List 和 List> ,我可以编写如下内容: import java.util.*; public class Test{ public static voi
第一个Dictionary就像 Dictionary ParentDict = new Dictionary(); ParentDict.Add("A_1", "1")
这是我的 jsp 文件: 我遇到了错误 The method replace(String, String, String) in the type Functions is not appl
我需要一些帮助。我有一个方法应该输出一个包含列表内容的 txt 文件(每行中的每个项目)。列表项是字符串数组。问题是,当我调用 string.Join 时,它返回文字字符串 "System.Strin
一位同事告诉我,使用以下方法: string url = "SomeURL"; string ext = "SomeExt"; string sub = "SomeSub"; string s
给定类: public class CategoryValuePair { String category; String value; } 还有一个方法: public
我正在尝试合并 Stream>>对象与所有 Streams 中的键一起映射到单个映射中. 例如, final Map someObject; final List>> list = someObjec
在这里使用 IDictionary 的值(value)是什么? 最佳答案 使用接口(interface)的值(value)始终相同:切换到另一个后端实现时,您不必更改客户端代码。 请考虑稍后分析您的代
我可以知道这两个字典声明之间的区别吗? var places = [String: String]() var places = [Dictionary()] 为什么当我尝试以这种方式附加声明时,只有
在 .NET 4.0 及更高版本中存在 string.IsNullOrWhiteSpace(string) 时,在检查字符串时使用 string.IsNullOrEmpty(string) 是否被视为
这个名字背后的原因是什么? SS64在 PowerShell 中解释此处的字符串如下: A here string is a single-quoted or double-quoted string
我打算离开 this 文章,尝试编写一个接受字符串和 &str 的函数,但我遇到了问题。我有以下功能: pub fn new(t_num: S) -> BigNum where S: Into {
我有一个结构为 [String: [String: String]] 的多维数组。我可以使用 for 循环到达 [String: String] 位,但我不知道如何访问主键(这个位 [String:
我正在尝试使用 sarama(管理员模式)创建主题。没有 ConfigEntries 工作正常。但我需要定义一些配置。 我设置了主题配置(这里发生了错误): tConfigs := map[s
我是一名优秀的程序员,十分优秀!