Самый быстрый способ вернуть список строк, используя подстановочный знак из коллекции в Java

Question

У меня есть набор 100000 строк.И, например, я хочу получить все строки, начинающиеся с "JO" из этого набора.Что было бы лучшим решением для этого?

Я думал Aho-Corasick, но у меня есть реализация , которая не поддерживает подстановочные знаки.

Answer 1

Если вы хотите, чтобы все строки начинались с последовательности, вы можете добавить всю строку в NavigableSet, например TreeSet, и получить subSet(text, text+'\uFFFF'), который даст вам все записи, начинающиеся с text Этот поиск равен O (log n)

---

Если вы хотите, чтобы все строки заканчивались последовательностью, вы можете сделать то же самое, за исключением того, что вы должны обратить строку. В этом случае лучше всего использовать TreeMap из перевернутой строки в прямую строку.

Если вы хотите «x * z», вы можете выполнить поиск по первому набору и получить объединение со значениями карты.

если вы хотите, чтобы он содержал « x », вы можете использовать Navigable >, где ключом является каждая строка, начиная с первого, второго, третьего символа и т. Д. Установите как вы можете получить дубликаты. Вы можете сделать поиск, как начинается со структуры.

Answer 2

Вот пользовательский класс соответствия, который выполняет сопоставление без регулярных выражений (для более точного выражения он использует регулярное выражение в конструкторе) и поддерживает сопоставление с подстановочными знаками:

public class WildCardMatcher {
    private Iterable<String> patternParts;
    private boolean openStart;
    private boolean openEnd;

    public WildCardMatcher(final String pattern) {
        final List<String> tmpList = new ArrayList<String>(
                                     Arrays.asList(pattern.split("\\*")));
        while (tmpList.remove("")) { /* remove empty Strings */ }
        // these last two lines can be made a lot simpler using a Guava Joiner
        if (tmpList.isEmpty())
            throw new IllegalArgumentException("Invalid pattern");
        patternParts = tmpList;
        openStart = pattern.startsWith("*");
        openEnd = pattern.endsWith("*");
    }

    public boolean matches(final String item) {
        int index = -1;
        int nextIndex = -1;
        final Iterator<String> it = patternParts.iterator();
        if (it.hasNext()) {
            String part = it.next();
            index = item.indexOf(part);
            if (index < 0 || (index > 0 && !openStart))
                return false;
            nextIndex = index + part.length();
            while (it.hasNext()) {
                part = it.next();
                index = item.indexOf(part, nextIndex);
                if (index < 0)
                    return false;
                nextIndex = index + part.length();
            }
            if (nextIndex < item.length())
                return openEnd;
        }
        return true;
    }

}

Вот некоторый тестовый код:

public static void main(final String[] args) throws Exception {
    testMatch("foo*bar", "foobar", "foo123bar", "foo*bar", "foobarandsomethingelse");
    testMatch("*.*", "somefile.doc", "somefile", ".doc", "somefile.");
    testMatch("pe*", "peter", "antipeter");
}

private static void testMatch(final String pattern, final String... words) {
    final WildCardMatcher matcher = new WildCardMatcher(pattern);
    for (final String word : words) {
        System.out.println("Pattern " + pattern + " matches word '"
                          + word + "': " + matcher.matches(word));
    }
}

Выход:

Pattern foo*bar matches word 'foobar': true
Pattern foo*bar matches word 'foo123bar': true
Pattern foo*bar matches word 'foo*bar': true
Pattern foo*bar matches word 'foobarandsomethingelse': false
Pattern *.* matches word 'somefile.doc': true
Pattern *.* matches word 'somefile': false
Pattern *.* matches word '.doc': true
Pattern *.* matches word 'somefile.': true
Pattern pe* matches word 'peter': true
Pattern pe* matches word 'antipeter': false

Хотя это далеко не готово к производству, оно должно быть достаточно быстрым и поддерживать несколько групповых символов (в том числе в первом и последнем месте). Но, конечно, если ваши символы подстановки только в конце, используйте ответ Питера (+1).