在树中搜索模式的算法
Algorithm for searching for patterns in trees
我正在从事一个大量使用树结构进行数据处理的项目。我正在寻找一种在树中查找匹配模式的方法。例如，考虑这样一棵树：
(1:a) ----- (2:b) ---- (4:c) ---- (5:e) ---- (8:c) ---- (9:f)
|---- (3:d) |--- (6:f) |--- (10:g)
|--- (7:g)
（1 有两个 children 2 和 3，4 有 children 5,6,7，8 有 children 9 和 10），字母是值每个节点的。
我需要找到所有出现的类似
的东西
c ---- f
|--- g
应该return4和8作为parent节点的索引。什么是好的算法？可能是BFS，但是有没有更专业的搜索算法来进行这种搜索？
想法 1
一种提高速度的简单方法是预先计算从每个字母到树中出现该字母的所有位置的列表的映射。
因此在您的示例中，c 将映射到 [4,8]。
然后当您搜索给定模式时，您将只需要探索至少第一个元素正确的子树。
想法 2
对此可能有助于某些使用模式的扩展是预先计算从每个字母到树中出现该字母的所有位置的 parents 列表的第二个映射。
例如，f 将映射到 [4,8]，e 将映射到 [4]。
如果位置列表按排序顺序存储，则这些地图可用于有效地查找具有头部和特定 children 的模式。
我们通过使用第一个地图查找头部获得可能位置的列表，并使用第二个地图查找其他列表children。
然后您可以合并这些列表（这可以高效完成，因为列表已排序）以查找出现在每个列表中的条目 - 这些将是所有匹配的位置。
这是我的一些理论构想，如有错误，请随时指正。
它受 prefix/suffix trie 结构的影响，该结构使人们能够在字符串中找到匹配的子字符串。虽然我会选择的Data Structure会比较tree-like，但本质上也会很graph-like，通过连接节点的引用
输出将最终（希望）快速显示包含该模式的 sub-tree 根的所有索引。
我将决定使用的数据结构类似于一个树节点，它包含字符串值、出现这种情况的每个位置的索引、包含公共节点的所有可能 parent 的索引值和子项存储为 O(1) 最佳案例搜索的地图。
以下所有代码均在 C# 中完成。
public class Node
{
public String value; //This will be the value. ie: “a”
public Dictionary<int, int> connections; //connections will hold {int reference (key), int parent (value)} pairs
public Dictionary<String, Node> childs; //This will contain all childs, with it’s value
//as the key.
public Node()
{
connections = new Dictionary<int, int>();
childs = new Dictionary<String, Node>();
}
}
其次，我们假设您的基础数据是一个非常传统的树结构，尽管可能会有一些差异。
public class TreeNode
{
public int index;
public String value;
public List<TreeNode> childs;
public TreeNode()
{
childs = new List<TreeNode>();
}
public TreeNode(String value)
{
childs = new List<TreeNode>();
this.value = value;
}
public void add(String name)
{
TreeNode child = new TreeNode(name);
childs.Add(child);
}
}
最后，基本 TreeNode 结构的节点都被索引了（在您的示例中，您使用了基于 1 的索引，但以下是在基于 0 的索引中完成的）
int index = 0;
Queue<TreeNode> tempQ = new Queue<TreeNode>();
tempQ.Enqueue(root);
while (tempQ.Count > 0)
{
temp = tempQ.Dequeue();
temp.index = index;
index++;
foreach (TreeNode tn in temp.childs)
{
tempQ.Enqueue(tn);
}
}
return root;
初始化我们的结构后，假设基础数据存储在传统类型的TreeNode结构中，我们将尝试做三件事：
使用基础 TreeNode
一个最大的属性是唯一值只会在一个节点中表示。例如，您的示例中的 {C}、{F} 和 {G} 将分别用一个节点表示，而不是两个。 （简单地说，所有具有共同值的节点将被归为一个。）
所有唯一节点（来自步骤 2）将附加到根元素，我们将通过将引用连接到引用来 "rebuild" 树。 （图形表示如下所示）
这是在 C# 中构建结构的代码，在 O(n):
中完成
private Node convert(TreeNode root)
{
Node comparisonRoot = new Node(); //root of our new comparison data structure.
//this main root will contain no data except
//for childs inside its child map, which will
//contain all childs with unique values.
TreeNode dataNode = root; //Root of base data.
Node workingNode = new Node(); //workingNode is our data structure's
//copy of the base data tree's root.
workingNode.value = root.value;
workingNode.connections.Add(0, -1);
// add workingNode to our data structure, because workingNode.value
// is currently unique to the empty map of the root's child.
comparisonRoot.childs.Add(workingNode.value, workingNode);
Stack<TreeNode> s = new Stack<TreeNode>();
s.Push(dataNode); //Initialize stack with root.
while (s.Count > 0) { //Iteratively traverse the tree using a stack
TreeNode temp = s.Pop();
foreach(TreeNode tn in temp.childs) {
//fill stack with childs
s.Push(tn);
}
//update workingNode to be the "parent" of the upcoming childs.
workingNode = comparisonRoot.childs[temp.value];
foreach(TreeNode child in temp.childs) {
if(!comparisonRoot.childs.ContainsKey(child.value)) {
//if value of the node is unique
//create a new node for the unique value
Node tempChild = new Node();
tempChild.value = child.value;
//store the reference/parent pair
tempChild.connections.Add(child.index, temp.index);
//because we are working with a unique value that first appeared,
//add the node to the parent AND the root.
workingNode.childs.Add(tempChild.value, tempChild);
comparisonRoot.childs.Add(tempChild.value, tempChild);
} else {
//if value of node is not unique (it already exists within our structure)
//update values, no need to create a new node.
Node tempChild = comparisonRoot.childs[child.value];
tempChild.connections.Add(child.index, temp.index);
if (!workingNode.childs.ContainsKey(tempChild.value)) {
workingNode.childs.Add(tempChild.value, tempChild);
}
}
}
}
return comparisonRoot;
}
所有唯一值都附加到一个non-valued根节点，只是为了将此根节点用作地图以快速跳转到任何引用。 （如下图）
在这里，您可以看到所有连接都是基于原始示例树进行的，只是每个唯一值只有一个节点实例。最后，您可以看到所有节点也都连接到根。
重点是每个唯一副本只有 1 个真实节点 object，并通过引用其他节点作为子节点来指向所有可能的连接。有点像有根的图结构
每个节点将包含所有 {[index], [parent index]}.
对
这是此数据结构的字符串表示形式：
Childs { A, B, D, C, E, F, G }
Connections { A=[0, -1]; B=[1, 0]; D=[2, 0]; C=[3, 1][7, 4];
E=[4, 3]; F=[5, 3][8, 7]; G=[6, 3][9, 7] }
在这里，您可能首先注意到的是节点 A（在您的示例中没有真正的 parent）的 parent 索引为 -1。它只是简单地说明节点 A 没有更多 parent 并且是根。
您可能注意到的其他事情是 C 的索引值为 3 和 7，分别连接到 1 和 4，您可以看到是节点 B 和节点 E（如果这不成立，请检查您的示例意义)
希望这是对结构的一个很好的解释。
那么我为什么要决定使用这个结构，这将如何帮助找到与特定模式匹配时的节点索引？
类似于后缀尝试，我认为最优雅的解决方案是 return 全部 "successful searches" 在一次操作中，而不是遍历所有节点以查看每个节点是否成功搜索（蛮力）。
下面是搜索的工作方式。
假设我们有模式
c ---- f
|--- g
来自示例。
在递归方法中，只留下 return 所有可能的 parentIndex（从我们的 [index, parentIndex] 对中检索）。
之后，在自然DFS类型的遍历中，C将同时收到F和G的return值。
在这里，我们对所有的孩子做一个交集运算（AND 运算），看看parent集合共有哪些索引。
接下来，我们进行另一个 AND 运算，这次是在上一步的结果与所有可能的 C（我们当前分支的）之间 index。
通过这样做，我们现在拥有一组包含 G 和 F 的所有可能的 C 索引。
虽然该模式只有 2 层深，但如果我们正在查看更深层次的模式，我们只需获取 C 索引的结果集，利用我们的结果索引找到所有 parent 对结果索引[index, parentIndex] 映射和 return 一组 parent 索引和 return 到此方法的第 2 步。 （看到递归了吗？）
这是刚刚解释的 C# 实现。
private HashSet<int> search(TreeNode pattern, Node graph, bool isRoot)
{
if (pattern.childs.Count == 0)
{
//We are at a leaf, return the set of parents values.
HashSet<int> set = new HashSet<int>();
if (!isRoot)
{
//If we are not at the root of the pattern, we return the possible
//index of parents that can hold this leaf.
foreach (int i in graph.connections.Keys)
{
set.Add(graph.connections[i]);
}
}
else
{
//However if we are at the root of the pattern, we don't want to
//return the index of parents. We simply return all indexes of this leaf.
foreach (int i in graph.connections.Keys)
{
set.Add(i);
}
}
return set;
}
else
{
//We are at a branch. We recursively call this method to the
//leaves.
HashSet<int> temp = null;
foreach(TreeNode tn in pattern.childs) {
String value = tn.value;
//check if our structure has a possible connection with the next node down the pattern.
//return empty set if connection not found (pattern does not exist)
if (!graph.childs.ContainsKey(value)){
temp = new HashSet<int>();
return temp;
}
Node n = graph.childs[value];
//Simply recursively call this method to the leaves, and
//we do an intersection operation to the results of the
//recursive calls.
if (temp == null)
{
temp = search(tn, n, false);
}
else
{
temp.IntersectWith(search(tn, n, false));
}
}
//Now that we have the result of the intersection of all the leaves,
//we do a final intersection with the result and the current branch's
//index set.
temp.IntersectWith(graph.connections.Keys);
//Now we have all possible indexes. we have to return the possible
//parent indexes.
if (isRoot)
{
//However if we are at the root of the pattern, we don't want to
//return the parent index. We return the result of the intersection.
return temp;
}
else
{
//But if we are not at the root of the pattern, we return the possible
//index of parents.
HashSet<int> returnTemp = new HashSet<int>();
foreach (int i in temp)
{
returnTemp.Add(graph.connections[i]);
}
return returnTemp;
}
}
}
要调用此方法，只需
//pattern - root of the pattern, TreeNode object
//root - root of our generated structure, which was made with the compare() method
//boolean - a helper boolean just so the final calculation will return its
// own index as a result instead of its parent's indices
HashSet<int> answers = search(pattern, root.childs[pattern.value], true);
哎呀，答案很长，我什至不确定这是否和其他算法一样有效！我也确信有马是在更大的树中搜索子树的更有效和优雅的方法，但这是我想到的一种方法！欢迎留下任何批评、建议、编辑或优化我的解决方案:)
我正在从事一个大量使用树结构进行数据处理的项目。我正在寻找一种在树中查找匹配模式的方法。例如，考虑这样一棵树：
(1:a) ----- (2:b) ---- (4:c) ---- (5:e) ---- (8:c) ---- (9:f)
|---- (3:d) |--- (6:f) |--- (10:g)
|--- (7:g)
（1 有两个 children 2 和 3，4 有 children 5,6,7，8 有 children 9 和 10），字母是值每个节点的。
我需要找到所有出现的类似
的东西 c ---- f
|--- g
应该return4和8作为parent节点的索引。什么是好的算法？可能是BFS，但是有没有更专业的搜索算法来进行这种搜索？
想法 1
一种提高速度的简单方法是预先计算从每个字母到树中出现该字母的所有位置的列表的映射。
因此在您的示例中，c 将映射到 [4,8]。
然后当您搜索给定模式时，您将只需要探索至少第一个元素正确的子树。
想法 2
对此可能有助于某些使用模式的扩展是预先计算从每个字母到树中出现该字母的所有位置的 parents 列表的第二个映射。
例如，f 将映射到 [4,8]，e 将映射到 [4]。
如果位置列表按排序顺序存储，则这些地图可用于有效地查找具有头部和特定 children 的模式。
我们通过使用第一个地图查找头部获得可能位置的列表，并使用第二个地图查找其他列表children。
然后您可以合并这些列表（这可以高效完成，因为列表已排序）以查找出现在每个列表中的条目 - 这些将是所有匹配的位置。
这是我的一些理论构想，如有错误，请随时指正。
它受 prefix/suffix trie 结构的影响，该结构使人们能够在字符串中找到匹配的子字符串。虽然我会选择的Data Structure会比较tree-like，但本质上也会很graph-like，通过连接节点的引用
输出将最终（希望）快速显示包含该模式的 sub-tree 根的所有索引。
我将决定使用的数据结构类似于一个树节点，它包含字符串值、出现这种情况的每个位置的索引、包含公共节点的所有可能 parent 的索引值和子项存储为 O(1) 最佳案例搜索的地图。
以下所有代码均在 C# 中完成。
public class Node
{
public String value; //This will be the value. ie: “a”
public Dictionary<int, int> connections; //connections will hold {int reference (key), int parent (value)} pairs
public Dictionary<String, Node> childs; //This will contain all childs, with it’s value
//as the key.
public Node()
{
connections = new Dictionary<int, int>();
childs = new Dictionary<String, Node>();
}
}
其次，我们假设您的基础数据是一个非常传统的树结构，尽管可能会有一些差异。
public class TreeNode
{
public int index;
public String value;
public List<TreeNode> childs;
public TreeNode()
{
childs = new List<TreeNode>();
}
public TreeNode(String value)
{
childs = new List<TreeNode>();
this.value = value;
}
public void add(String name)
{
TreeNode child = new TreeNode(name);
childs.Add(child);
}
}
最后，基本 TreeNode 结构的节点都被索引了（在您的示例中，您使用了基于 1 的索引，但以下是在基于 0 的索引中完成的）
int index = 0;
Queue<TreeNode> tempQ = new Queue<TreeNode>();
tempQ.Enqueue(root);
while (tempQ.Count > 0)
{
temp = tempQ.Dequeue();
temp.index = index;
index++;
foreach (TreeNode tn in temp.childs)
{
tempQ.Enqueue(tn);
}
}
return root;
初始化我们的结构后，假设基础数据存储在传统类型的TreeNode结构中，我们将尝试做三件事：
使用基础
TreeNode 构建 graph-like 结构
一个最大的属性是唯一值只会在一个节点中表示。例如，您的示例中的 {C}、{F} 和 {G} 将分别用一个节点表示，而不是两个。 （简单地说，所有具有共同值的节点将被归为一个。）
所有唯一节点（来自步骤 2）将附加到根元素，我们将通过将引用连接到引用来 "rebuild" 树。 （图形表示如下所示）
这是在 C# 中构建结构的代码，在 O(n):
private Node convert(TreeNode root)
{
Node comparisonRoot = new Node(); //root of our new comparison data structure.
//this main root will contain no data except
//for childs inside its child map, which will
//contain all childs with unique values.
TreeNode dataNode = root; //Root of base data.
Node workingNode = new Node(); //workingNode is our data structure's
//copy of the base data tree's root.
workingNode.value = root.value;
workingNode.connections.Add(0, -1);
// add workingNode to our data structure, because workingNode.value
// is currently unique to the empty map of the root's child.
comparisonRoot.childs.Add(workingNode.value, workingNode);
Stack<TreeNode> s = new Stack<TreeNode>();
s.Push(dataNode); //Initialize stack with root.
while (s.Count > 0) { //Iteratively traverse the tree using a stack
TreeNode temp = s.Pop();
foreach(TreeNode tn in temp.childs) {
//fill stack with childs
s.Push(tn);
}
//update workingNode to be the "parent" of the upcoming childs.
workingNode = comparisonRoot.childs[temp.value];
foreach(TreeNode child in temp.childs) {
if(!comparisonRoot.childs.ContainsKey(child.value)) {
//if value of the node is unique
//create a new node for the unique value
Node tempChild = new Node();
tempChild.value = child.value;
//store the reference/parent pair
tempChild.connections.Add(child.index, temp.index);
//because we are working with a unique value that first appeared,
//add the node to the parent AND the root.
workingNode.childs.Add(tempChild.value, tempChild);
comparisonRoot.childs.Add(tempChild.value, tempChild);
} else {
//if value of node is not unique (it already exists within our structure)
//update values, no need to create a new node.
Node tempChild = comparisonRoot.childs[child.value];
tempChild.connections.Add(child.index, temp.index);
if (!workingNode.childs.ContainsKey(tempChild.value)) {
workingNode.childs.Add(tempChild.value, tempChild);
}
}
}
}
return comparisonRoot;
}
所有唯一值都附加到一个non-valued根节点，只是为了将此根节点用作地图以快速跳转到任何引用。 （如下图）
在这里，您可以看到所有连接都是基于原始示例树进行的，只是每个唯一值只有一个节点实例。最后，您可以看到所有节点也都连接到根。
重点是每个唯一副本只有 1 个真实节点 object，并通过引用其他节点作为子节点来指向所有可能的连接。有点像有根的图结构
每个节点将包含所有 {[index], [parent index]}.
这是此数据结构的字符串表示形式：
Childs { A, B, D, C, E, F, G }
Connections { A=[0, -1]; B=[1, 0]; D=[2, 0]; C=[3, 1][7, 4];
E=[4, 3]; F=[5, 3][8, 7]; G=[6, 3][9, 7] }
在这里，您可能首先注意到的是节点 A（在您的示例中没有真正的 parent）的 parent 索引为 -1。它只是简单地说明节点 A 没有更多 parent 并且是根。
您可能注意到的其他事情是 C 的索引值为 3 和 7，分别连接到 1 和 4，您可以看到是节点 B 和节点 E（如果这不成立，请检查您的示例意义)
希望这是对结构的一个很好的解释。
那么我为什么要决定使用这个结构，这将如何帮助找到与特定模式匹配时的节点索引？
类似于后缀尝试，我认为最优雅的解决方案是 return 全部 "successful searches" 在一次操作中，而不是遍历所有节点以查看每个节点是否成功搜索（蛮力）。
下面是搜索的工作方式。
假设我们有模式
c ---- f
|--- g
来自示例。
在递归方法中，只留下 return 所有可能的 parentIndex（从我们的 [index, parentIndex] 对中检索）。
之后，在自然DFS类型的遍历中，C将同时收到F和G的return值。
在这里，我们对所有的孩子做一个交集运算（AND 运算），看看parent集合共有哪些索引。
接下来，我们进行另一个 AND 运算，这次是在上一步的结果与所有可能的 C（我们当前分支的）之间 index。
通过这样做，我们现在拥有一组包含 G 和 F 的所有可能的 C 索引。
虽然该模式只有 2 层深，但如果我们正在查看更深层次的模式，我们只需获取 C 索引的结果集，利用我们的结果索引找到所有 parent 对结果索引[index, parentIndex] 映射和 return 一组 parent 索引和 return 到此方法的第 2 步。 （看到递归了吗？）
这是刚刚解释的 C# 实现。
private HashSet<int> search(TreeNode pattern, Node graph, bool isRoot)
{
if (pattern.childs.Count == 0)
{
//We are at a leaf, return the set of parents values.
HashSet<int> set = new HashSet<int>();
if (!isRoot)
{
//If we are not at the root of the pattern, we return the possible
//index of parents that can hold this leaf.
foreach (int i in graph.connections.Keys)
{
set.Add(graph.connections[i]);
}
}
else
{
//However if we are at the root of the pattern, we don't want to
//return the index of parents. We simply return all indexes of this leaf.
foreach (int i in graph.connections.Keys)
{
set.Add(i);
}
}
return set;
}
else
{
//We are at a branch. We recursively call this method to the
//leaves.
HashSet<int> temp = null;
foreach(TreeNode tn in pattern.childs) {
String value = tn.value;
//check if our structure has a possible connection with the next node down the pattern.
//return empty set if connection not found (pattern does not exist)
if (!graph.childs.ContainsKey(value)){
temp = new HashSet<int>();
return temp;
}
Node n = graph.childs[value];
//Simply recursively call this method to the leaves, and
//we do an intersection operation to the results of the
//recursive calls.
if (temp == null)
{
temp = search(tn, n, false);
}
else
{
temp.IntersectWith(search(tn, n, false));
}
}
//Now that we have the result of the intersection of all the leaves,
//we do a final intersection with the result and the current branch's
//index set.
temp.IntersectWith(graph.connections.Keys);
//Now we have all possible indexes. we have to return the possible
//parent indexes.
if (isRoot)
{
//However if we are at the root of the pattern, we don't want to
//return the parent index. We return the result of the intersection.
return temp;
}
else
{
//But if we are not at the root of the pattern, we return the possible
//index of parents.
HashSet<int> returnTemp = new HashSet<int>();
foreach (int i in temp)
{
returnTemp.Add(graph.connections[i]);
}
return returnTemp;
}
}
}
要调用此方法，只需
//pattern - root of the pattern, TreeNode object
//root - root of our generated structure, which was made with the compare() method
//boolean - a helper boolean just so the final calculation will return its
// own index as a result instead of its parent's indices
HashSet<int> answers = search(pattern, root.childs[pattern.value], true);
哎呀，答案很长，我什至不确定这是否和其他算法一样有效！我也确信有马是在更大的树中搜索子树的更有效和优雅的方法，但这是我想到的一种方法！欢迎留下任何批评、建议、编辑或优化我的解决方案:)