在一个字符串中搜索多个字符串的最快方法

Question

以下是我用来在单个给定字符串中查找所有子字符串出现次数的代码。

public static void main(String... args) {
    String fullString = "one is a good one. two is ok. three is three. four is four. five is not four";
    String[] severalStringArray = { "one", "two", "three", "four" };
    Map<String, Integer> countMap = countWords(fullString, severalStringArray);
}

public static Map<String, Integer> countWords(String fullString, String[] severalStringArray) {
    Map<String, Integer> countMap = new HashMap<>();

    for (String searchString : severalStringArray) {
        if (countMap.containsKey(searchString)) {
            int searchCount = countMatchesInString(fullString, searchString);
            countMap.put(searchString, countMap.get(searchString) + searchCount);
        } else
            countMap.put(searchString, countMatchesInString(fullString, searchString));
    }

    return countMap;
}

private static int countMatchesInString(String fullString, String subString) {
    int count = 0;
    int pos = fullString.indexOf(subString);
    while (pos > -1) {
        count++;
        pos = fullString.indexOf(subString, pos + 1);
    }
    return count;
}

假设完整字符串可能是作为一个字符串读取的整个文件。上述方法是否是高效的搜索方式，或者有更好或更快的方法可以实现呢？

谢谢。

- integ specialist

---

你可以寻找 Trie 数据结构来降低时间复杂度。 - Ashishkumar Singh

你可以使用 Knuth-Morris-Pratt 算法进行字符串匹配。 - Deepeshkumar

要明确一点，你所问的问题是关于在另一个字符串中计算多个字符串出现次数的。这意味着简单的解决方案，如正则表达式等并不适用。 - Stephen C

还要注意搜索字符串重叠的情况，例如 {"one","onerous"}。这几乎排除了使用带有交替项的正则表达式的可能性。 - Stephen C

@Deepeshkumar 我们需要一个带有代码片段的示例。算法对于开发人员来说太复杂了，难以理解和实现。如果您分享一个示例，那将非常容易理解或者明白。 - integ specialist

@integspecialist 是的，你说得对。我正在发布算法代码的链接，这是我理解、修改和实现的方式。链接： https://codereview.stackexchange.com/q/265575/175198 - Deepeshkumar

Answer 1

您可以将要搜索的单词形成正则表达式的分支结构，然后对该正则表达式进行一次搜索：

public static int matchesInString(String fullString, String regex) {
    int count = 0;

    Pattern r = Pattern.compile(regex);
    Matcher m = r.matcher(fullString);

    while (m.find())
        ++count;

    return count;
}

String fullString = "one is a good one. two is ok. three is three. four is four. five is not four";
String[] severalStringArray = { "one", "two", "three", "four" };
String regex = "\\b(?:" + String.join("|", severalStringArray) + ")\\b";

int count = matchesInString(fullString, regex);
System.out.println("There were " + count + " matches in the input");

这将打印：

输入中有 8 个匹配项

请注意，上面示例中使用的正则表达式模式是：

\b(?:one|two|three|four)\b

- Tim Biegeleisen

---

我尝试了正则表达式和模式匹配，发现在处理大文件字符串时速度很慢。你在处理大文件时也遇到了速度问题吗？ - integ specialist

问题是在Java中，indexOf、Regex或contains哪一个在大字符串中搜索更快应该被探索或验证。 - integ specialist

Answer 2

正则表达式

你可以使用正则表达式（regex）解决你的问题。正则表达式是一种工具，帮助你匹配字符串中的模式。这个模式可以是一个单词或一组字符。

Java中的正则表达式

在Java中，有两个对象可以帮助你处理正则表达式：Pattern和Matcher。

下面是一个示例，演示如何在Java中搜索字符串stackoverflowXstackoverflowXXXstackoverflowXX中是否存在单词stackoverflow。

String pattern = "stackoverflow";
String stringToExamine = "stackoverflowXstackoverflowXXXstackoverflowXX";

Pattern patternObj = Pattern.compile(pattern);
Matcher matcherObj = patternObj.matcher(stringToExamine);

统计给定字符串中某个单词出现的次数

根据您使用的Java版本，这里提供了不同的解决方案：

Java 9+

long matches = matcherObj.results().count();

Older Java versions

int count = 0;
while (matcherObj.find())
    count++;

在问题中使用正则表达式

您使用一种计算文本（字符串）中单词出现次数的方法，您可以像这样进行修改：

Java 9+

public static int matchesInString(String fullString, String pattern)
{
    Pattern patternObj = Pattern.compile(pattern);
    Matcher matcherObj = patternObj.matcher(fullString);
    
    return matcherObj.results().count();
}

旧版Java

public static int matchesInString(String fullString, String pattern)
{
    int count = 0;

    Pattern patternObj = Pattern.compile(pattern);
    Matcher matcherObj = patternObj.matcher(fullString);
    
    while (matcherObj.find())
        count++;
        
    return count;
}

- Marte Valerio Falcone

Answer 3

有人评论了一个Trie树的实现。我不知道它是否快速。

static class Trie {

    static final long INC_NODE_NO = 1L << Integer.SIZE;

    private long nextNodeNo = 0;
    private Node root = new Node();
    private final Map<Long, Node> nodes = new HashMap<>();

    public void put(String word) {
        Node node = root;
        for (int i = 0, len = word.length(); i < len; ++i)
            node = node.put(word.charAt(i));
        node.data = word;
    }

    public List<String> findPrefix(String text, int start) {
        List<String> result = new ArrayList<>();
        Node node = root;
        for (int i = start, length = text.length(); i < length; ++i) {
            if ((node = node.get(text.charAt(i))) == null)
                break;
            String v = node.data;
            if (v != null)
                result.add(v);
        }
        return result;
    }

    public Map<String, Integer> find(String text) {
        Map<String, Integer> result = new HashMap<>();
        for (int i = 0, length = text.length(); i < length; ++i)
            for (String w : findPrefix(text, i))
                result.compute(w, (k, v) -> v == null ? 1 : v + 1);
        return result;
    }

    class Node {
        final long no;
        String data;

        Node() {
            this.no = nextNodeNo;
            nextNodeNo += INC_NODE_NO;
        }

        Node get(int key) {
            return nodes.get(no | key);
        }

        Node put(int key) {
            return nodes.computeIfAbsent(no | key, k -> new Node());
        }
    }
}

public static void main(String args[]) throws IOException {
    String fullString = "one is a good one. two is ok. three is three. four is four. five is not four";
    String[] severalStringArray = { "one", "two", "three", "four" };
    Trie trie = new Trie();
    for (String word : severalStringArray)
        trie.put(word);
    Map<String, Integer> count = trie.find(fullString);
    System.out.println(count);
}

输出：

{four=3, one=2, three=2, two=1}

- user4910279

Answer 4

实际上，最快的方法是先扫描字符串并计算所有已存在的单词，并将其保存到Map中。然后只选择所需的单词。

简单点！对于这个简单的任务，正则表达式太复杂且效率不高。让我们用锤子来解决它吧！

public static void main(String... args) {
    String str = "one is a good one. two is ok. three is three. four is four. five is not four";
    Set<String> words = Set.of("one", "two", "three", "four");
    Map<String, Integer> map = countWords(str, words);
}

public static Map<String, Integer> countWords(String str, Set<String> words) {
    Map<String, Integer> map = new HashMap<>();

    for (int i = 0, j = 0; j <= str.length(); j++) {
        char ch = j == str.length() ? '\0' : str.charAt(j);

        if (j == str.length() || !isWordSymbol(ch)) {
            String word = str.substring(i, j);

            if (!word.isEmpty() && words.contains(word))
                map.put(word, map.getOrDefault(word, 0) + 1);

            i = j + 1;
        }
    }

    return map;
}

private static boolean isWordSymbol(char ch) {
    return Character.isLetter(ch) || ch == '-' || ch == '_';
}

- oleg.cherednik

---

创建子字符串不会创建一个不可变对象吗？相比于indexOf，它的性能确实更好吗？上述方法解决了什么问题，而不是使用indexOf？ - integ specialist

"regexp" 过于复杂。我认为 "indexOf(char)" 不适合，因为你可能有很多字母和许多空格字符。 - oleg.cherednik