Может ли Java indexOf (метод грубой силы) быть более практичным для меня или какого-либо другого алгоритма подстроки?

Ответ 1

Вы можете заменить хэш-таблицу на Trie.

Разделите текст текста на слова, используя пробел для разделения слов. Затем проверьте, находится ли слово в Trie. Если он находится в Trie, обновите счетчик, связанный со словом. В идеале счетчик будет интегрирован в Trie.

Эта оценка O (C), где C - количество символов в тексте. Очень маловероятно, что вы можете избежать проверки каждого персонажа хотя бы один раз. Таким образом, этот подход должен быть таким же хорошим, как вы можете получить, по крайней мере, в терминах больших O.

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

Ответ 2

То, что вы описываете, звучит как отличный прецедент для алгоритма сопоставления строк Aho-Corasick. Этот алгоритм находит все совпадения набора строк шаблонов внутри исходной строки и делает это в линейном времени (плюс время, чтобы сообщить о совпадениях). Если у вас есть фиксированный набор строк для поиска, вы можете выполнить линейную предварительную обработку перед шаблонами для быстрого поиска всех совпадений.

Здесь есть Java-реализация Aho-Corasick. Я не пробовал, но это может быть хорошим совпадением.

Надеюсь, это поможет!

Ответ 3

Я уверен, что string.contains уже сильно оптимизирован, поэтому замена его чем-то другим не принесет вам много пользы.

Таким образом, я подозреваю, что не нужно искать каждое слово в ваших словах в чате, а делать несколько сравнений сразу.

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

Ответ 4

Вы можете создать индекс слов, который вам нужно совместить, и считать их при их обработке. Если вы можете использовать HashMap для поиска шаблонов для каждого слова, стоимость будет O(n * m)

Вы можете использовать HashMap для всех возможных слов, затем вы можете анализировать слова позже.

например. скажем, вам нужно сопоставить красный и яблочный, вы можете комбинировать сумму

redapple = 1
applered = 0
red = 10
apple = 15

Это означает, что красный цвет на самом деле равен 11 (10 + 1), а яблоко - 16 (15 + 1)

Ответ 5

Я не знаю корейский, поэтому я предполагаю, что те же стратегии, используемые для возиться со струнами на корейском языке, не обязательно возможны в том, как это происходит с английским языком, но, возможно, эта стратегия в псевдокоде может быть применена с вашими знаниями корейского языка сделай так, чтоб это работало. (Java, конечно, все тот же, но, к примеру, на корейском языке все еще очень вероятно, что буквы "должны" быть последовательными? Существуют ли даже буквы для "ough"? Но с этим, как мы надеемся, принцип может применять

Я бы использовал String.toCharArray для создания двумерного массива (или ArrayList, если требуется размер переменной).

if (first letter of word matches keyword first letter)//we have a candidate
    skip to last letter of the current word //see comment below
    if(last letter of word matches keyword last letter)//strong candidate
        iterate backwards to start+1 checking remainder of letters

Причина, по которой я предлагаю перейти к последнему письму, состоит в том, что статистически "согласный, гласный" для первых двух букв слова значительно высок, особенно существительные, которые будут состоять из многих ваших ключевых слов, поскольку любая пища является существительное (почти все приведенные вами примеры ключевых слов были сопоставлены с структурой согласного, гласной). И поскольку есть только 5 гласных (плюс y), вероятность того, что вторая буква "i" появится в ключевом слове "пицца", по своей природе весьма вероятна, но после этого момента все еще есть хорошая вероятность, что слово может получиться чтобы не быть совпадением.

Однако, если вы знаете, что первая буква и последняя буква совпадают, у вас, вероятно, есть гораздо более сильный кандидат, а затем можно повторить в обратном порядке. Я думаю, что по более крупным наборам данных это позволит устранить кандидатов намного быстрее, чем проверка букв в порядке. В принципе, вы позволите слишком многим поддельным кандидатам пройти вторую итерацию, тем самым увеличив ваши общие условные операции. Это может показаться чем-то маленьким, но в подобном проекте много повторений, поэтому микро-оптимизации будут накапливаться очень быстро.

Если этот подход может быть применен на языке, который, по-видимому, очень сильно отличается от английского (я имею в виду от невежества здесь), то я думаю, что это может обеспечить вам некоторую эффективность, если вы сделаете это через итерацию char массив или со сканером или любой другой конструкцией.

Ответ 6

Трюк заключается в том, чтобы понять, что если вы можете описать строку, которую ищете в качестве обычного выражения, вы также можете по определению описать ее с помощью конечного автомата.

На каждом символе вашего сообщения запускается конечный автомат для каждого из ваших 1600 шаблонов и пропускает через него символ. Это звучит страшно, но поверьте, большинство из них в любом случае прекратится, так что вы на самом деле не выполняете огромную работу. Имейте в виду, что конечный автомат обычно может быть закодирован с помощью простого переключателя/футляра или ch == s.charAt на каждом шаге, поэтому они близки к максимальной в легком весе.

Очевидно, что вы знаете, что делать, когда один из ваших поисковых машин заканчивается в конце поиска. Любой, который заканчивается перед полным совпадением, может быть немедленно отброшен.

private static class Matcher {
    private final int where;
    private final String s;
    private int i = 0;

    public Matcher ( String s, int where ) {
        this.s = s;
        this.where = where;
    }

    public boolean match(char ch) {
        return s.charAt(i++) == ch;
    }

    public int matched() {
        return i == s.length() ? where: -1;
    }
}

// Words I am looking for.
String[] watchFor = new String[] {"flies", "like", "arrow", "banana", "a"};
// Test string to search.
String test = "Time flies like an arrow, fruit flies like a banana";

public void test() {
    // Use a LinkedList because it is O(1) to remove anywhere.
    List<Matcher> matchers = new LinkedList<> ();
    int pos = 0;
    for ( char c : test.toCharArray()) {
        // Fire off all of the matchers at this point.
        for ( String s : watchFor ) {
            matchers.add(new Matcher(s, pos));
        }
        // Discard all matchers that fail here.
        for ( Iterator<Matcher> i = matchers.iterator(); i.hasNext(); ) {
            Matcher m = i.next();
            // Should it be removed?
            boolean remove = !m.match(c);
            if ( !remove ) {
                // Still matches! Is it complete?
                int matched = m.matched();
                if ( matched >= 0 ) {
                    // Todo - Should use getters.
                    System.out.println("    "+m.s +" found at "+m.where+" active matchers "+matchers.size());
                    // Complete!
                    remove = true;
                }
            }
            // Remove it where necessary.
            if ( remove ) {
                i.remove();
            }
        }
        // Step pos to keep track.
        pos += 1;
    }
}

печатает

flies found at 5 active matchers 6
like found at 11 active matchers 6
a found at 16 active matchers 2
a found at 19 active matchers 2
arrow found at 19 active matchers 6
flies found at 32 active matchers 6
like found at 38 active matchers 6
a found at 43 active matchers 2
a found at 46 active matchers 3
a found at 48 active matchers 3
banana found at 45 active matchers 6
a found at 50 active matchers 2

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

Ответ 7

Это довольно широкий вопрос, поэтому я не буду вдаваться в подробности, но грубо:

Предварительно обработайте стога сена, используя что-то вроде широкоформатного lemmatizer, чтобы создавать версии сообщений только "только для слов", отмечая, какие темы все слова в он покрывает. Например, любые случаи "гамбургера", "пиццы", "кокса", "обеда", "обеда", "ресторана" или "Макдональдса" приведут к тому, что "тема" "еда" будет собрана для этого сообщения, Некоторые слова могут иметь несколько тем, например, "Макдональдс" может быть в разделах "еда" и "бизнес". У большинства слов не будет темы.

После этого процесса у вас будут стога сена, состоящие только из слов "темы". Затем создайте Map<String, Set<Integer>> и заполните его словом темы и идентификаторами набора сообщений чата, которые его содержат. Это обратный индекс слова темы в сообщениях чата, которые его содержат.

Код времени выполнения для поиска всех документов, содержащих все n слов, является тривиальным и супер быстрым - рядом с O (#terms):

private Map<String, Set<Integer>> index; // pre-populated

Set<Integer> search(String... topics) {
    Set<Integer> results = null;
    for (String topic : topics) {
        Set<Integer> hits = index.get(topic);
        if (hits == null)
            return Collections.emptySet();
        if (results == null)
            results = new HashSet<Integer>(hits);
        else
            results.retainAll(hits);
        if (results.isEmpty())
            return Collections.emptySet(); // exit early
    }
    return results;
}

Это будет выполняться около O (1) и сообщит вам, какие сообщения имеют общие условия поиска. Если вы просто хотите номер, используйте тривиальный size() возвращаемого Set.