使用通配符值的Trie实现 [英] Trie implementation with wildcard values

问题描述

我正在实现一种算法来进行目录匹配。因此，我得到了一组有效的路径，其中可以包含通配符（用 X表示）。然后，当我传入一个输入时，我需要知道该输入是否与我的有效集中的路径之一匹配。当传入的通配符值实际上与另一个有效值匹配时，我遇到了通配符问题。这是一个示例：

I'm implementing an algorithm to do directory matching. So I'm given a set of valid paths that can include wildcards (denoted by "X"). Then when I pass in an input I need to know if that input matches with one of the paths in my valid set. I'm running into a problem with the wildcards when a wildcard value that is passed in actually matches with another valid value. Here is an example:

有效路径集：

/guest
/guest/X
/X/guest
/member
/member/friends
/member/X
/member/X/friends

示例输入：

/member/garbage/friends    
/member/friends/friends

这些都应返回true，但是只有第一个返回。在第一种情况下，因为垃圾与其他可能的路径不匹配，但是此时有通配符的选项，它将跳过并继续前进，然后看到朋友，并且知道这是匹配项。但是，我的第二种情况不起作用，因为它遇到了朋友并沿着我的特里的另一条路走了，而不是通配符路。因为在这个位置有一条与朋友在一起的有效路径，所以它认为应该是那样。然后它再次看到 friends，但是从这时开始，没有与 friends的有效路径，因此它返回false。

These should both return true, however only the first one does. In the first case because "garbage" does not match with another other possible paths but there is an option for a wildcard at this point it will skip it and move on, then it sees "friends" and it knows it's a match. However, my second case does not work because it sees friends and goes down a different path in my trie, not the wildcard path. Because there is a valid path with "friends" in this position it thinks it will be that. Then it sees "friends" again but from this point in the trie there are no valid paths with "friends" so it returns false.

我的问题是，即使在错误的分支中，我如何才能识别其他有效路径。我的搜索代码和示例trie图如下。

My question is, how can I get it to recognize the other valid path even when it goes down the wrong branch in the trie. My search code and example trie diagram is below.

我的trie的搜索算法如下：

The search algorithm for my trie is as follows:

private TrieNode searchNode(String input) {
    Map<String, TrieNode> children = root.children;
    TrieNode t = null;

    // break up input into individual tokens
    String[] tokenizedLine = input.split("/");
    for(int i = 0; i < tokenizedLine.length; i++){
        String current = tokenizedLine[i];

        if(children.containsKey(current)) {
            t = children.get(current);
            children = t.children;
        }else if(children.containsKey("X")){
            t = children.get("X");
            children = t.children;
        }else{
            return null;
        }
    }

    return t;
}

将使用示例路径集构建的特里图像：

当我输入/ member / friends / friends时，我的算法沿着突出显示的路径停止并停止，因为它之后没有看到其他 friends，而是如何能否将它的第一个朋友识别为通配符值，所以它将继续并在通配符之后看到第二个朋友？

An image of the trie that would be built with my sample path set: When I input /member/friends/friends my algorithm is going down the highlighted path and stopping because it does not see another "friends" after, but how can I get it to recognize the first "friends" as a wildcard value instead, so then it will continue and see the second "friends" after the wildcard?

任何帮助！

推荐答案

弄清楚了。我实现了一些回溯，以跟踪它看到两条可能路径的最后一个节点。如果它在一条路径上发现死角，它将回到上一次看到两条可能路径并尝试另一条路径的时间。新算法如下所示：

Figured it out. I implemented some backtracking to keep track of the last node where it saw two possible paths. If it finds a dead end on one path it will go back to the last time it saw two possible paths and try the other. New Algorithm looks like this:

private TrieNode searchNode(String input) {
        Map<String, TrieNode> children = root.children;
        TrieNode t = null;

        // Variables for backtrack function
        TrieNode alternativeWildcardNode = null;
        int wildcardIndex = 0;
        Map<String, TrieNode> wildcardChildren = root.children;

        // break up input into individual tokens
        String[] tokenizedLine = input.split("/");
        for(int i = 0; i < tokenizedLine.length; i++){
            String current = tokenizedLine[i];

            //System.out.println(current);
            //System.out.println(Integer.toString(i));

            if(children.containsKey(current) && children.containsKey("X")) {
                // store current variable state in case we need to back track here
                alternativeWildcardNode = children.get("X");
                wildcardIndex = i;
                wildcardChildren = alternativeWildcardNode.children;

                t = children.get(current);
                children = t.children;
            }else if(children.containsKey(current)) {
                t = children.get(current);
                children = t.children;
            }else if(children.containsKey("X")){
                t = children.get("X");
                children = t.children;
            }else if(alternativeWildcardNode != null){
                // if we've reached a branch with no match, but had a possible wildcard previously
                // call reset state to the wildcard option instead of static
                t = alternativeWildcardNode;
                alternativeWildcardNode = null;
                i = wildcardIndex;
                children = wildcardChildren;
            }else{
                return null;
            }
        }

        return t;
    }

这篇关于使用通配符值的Trie实现的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！