Поиск перестановок строк в наборе строк

Question

Название это довольно неловко; Я не был уверен, как подвести итог. Я знаю, как я могу это сделать, я просто не знаю, как это сделать эффективно. Вот моя проблема:

У меня есть строка в качестве ввода. Допустим,

Foo Bar

И у меня есть очень большой набор строк (десятки тысяч). Допустим,

фу, баз, бар, бла, фу бар, фу баз

Мне нужно сопоставить входные данные со строками в наборе. В этом случае «foo», «bar» и «foo bar» считаются совпадениями.

Итак, мне нужно либо как-то найти все перестановки ввода (это может быть длиннее 2 слов), либо как-то определить, намеревался ли пользователь поместить его (или часть) в кавычки. Или, может быть, сделать что-то, о чем я не думал.

Есть ли какая-то структура данных или алгоритм, который я могу использовать для этого? Как мне поступить, или я не должен обращаться с этим вариантом использования?

РЕДАКТИРОВАТЬ : выше опечатка, которая исказила проблему; в приведенном выше примере «foo baz» также совпадает. Извини за это. Я, по сути, хочу сопоставить любую перестановку входных слов со словарем. Таким образом, ввод «abc xyz» будет соответствовать «123 abc» или «abc xyz» или «xyz 123», но не «abcxyz».

Answer 1

Насколько велик ваш словарь? Вы можете преобразовать свой словарь в три. Там были сообщения людей, как преобразовать словарь в три. Как только вы это сделаете, поиск будет простым и быстрым.

Кроме того, простым решением может быть разбиение строки поиска на отдельные слова и поиск по каждому из них в вашем дереве, чтобы дубликаты не учитывались дважды.

Answer 2

Я бы предложил использовать словарь. Используйте строки в качестве ключей и список строк в качестве значения. Токенизируйте строки, по которым будет производиться поиск, и добавляйте всю строку в свой словарь по одному разу для каждого токена. (Вы можете использовать метод split для токенизации ваших строк. Используйте пробел в качестве разделителя.) После этого, когда вам нужно выполнить поиск, вы токенизируете строку поиска и выполняете поиск для каждого токена в вашем словаре.

Таким образом, если вы добавили следующие строки: foo, baz, bar, blah, foo bar, foo baz

Ваш словарь содержит записи:

foo: foo, foo bar, foo baz Баз: Баз, Фу Баз bar: bar, foo bar бла: бла

Если вы ищете "foo bar",

ваш вывод представляет собой объединение записей, хранящихся в foo и bar, примерно так: "foo bar": = foo, bar

foo: foo, foo bar, foo baz союз bar: bar, foo bar

подача: foo, foo bar, foo baz, bar

РЕДАКТИРОВАТЬ: Я только что заметил, что вы хотите только полное или частичное совпадение, то есть foo baz не является приемлемым. Простое решение - опубликовать результаты обработки - ограничить длинную строку поиска и целевую строку длиной более короткой, а затем сравнить усеченную строку с неизмененной строкой. Принимайте только те из них, которые эквивалентны.

РЕДАКТИРОВАТЬ: Таким образом, оказывается, Foo Baz действительно совпадает. Не обращайте внимания на параграф выше (первое редактирование). Смотрите (C #) код следующим образом:

class DictionarySearch
{
    private Dictionary<string, List<string>> dict;

    public DictionarySearch()
    {
        dict = new Dictionary<string, List<string>>();
    }

    /// <summary>
    /// Add a string e.g. foo bar to the dictionary
    /// </summary>
    /// <param name="s">string to be added</param>
    public void addString(string s)
    {
        //tokenize string
        string[] words = s.Split(new char[] { ' ' });

        //add each token to the dictionary as a key with the matching value being s
        foreach (string w in words)
        {
            if (dict.ContainsKey(w))
            {
                dict[w].Add(s);
            }
            else
            {
                dict.Add(w, new List<string>());
                dict[w].Add(s);
            }
        }
    }
    /// <summary>
    /// Find all strings which match at least one token
    /// </summary>
    /// <param name="s">string of tokens (words) to be matched</param>
    /// <returns>List of strings matching at least one word</returns>
    public IList<string> getMatches(string s)
    {
        //split search string into words
        string[] words = s.Split(new char[] { ' ' });
        List<string> output = new List<string>();

        //retrieve from dictionary list of strings matching each word.
        foreach (string w in words)
        {
            if (dict.ContainsKey(w))
            {
                output.AddRange(dict[w]);
            }
            else
            {
                continue;
            }
        }

        return output;
    }
}

При наличии словаря с m строками с q словами на строку и n уникальными словами и поисковой строкой с l словами временные сложности следующие:

Заполнить структуру данных: O (q m T [словарь-вставка]). Вставка должна быть выполнена для каждого слова

Найдите строку: O (l * T [dictionary-find]). Словарь поиска по слову в строке поиска.

Фактическая стоимость зависит от реализации вашего словаря. Словарь на основе хеш-таблицы несет O (1) стоимость как для вставки, так и для поиска. Словарь на основе двоичного дерева несет O (LG N) стоимость как для вставки, так и для поиска.

Answer 3

Для больших входных строк и словарей с многословными фразами используйте Rabin-Karp или Aho-Corasick algos.

(Ссылка на Рабина-Карпа - http://en.wikipedia.org/wiki/Rabin–Karp_string_search_algorithm - по какой-то причине я не смог получить ссылку на ссылку выше)

Answer 4

(Когда вы говорите «эффективный», вам, вероятно, нужно быть более явным с точки зрения пространства и времени. Допустим, вы имеете в виду эффективность времени (учитывая, что вы упомянули перестановки)).

Задача вычисления ответа на

String[] findStringsContaining(List<String> strings, String[] words)

может быть разделен и передан параллельным потокам выполнения, учитывая, что он является чисто функциональным и не имеет побочных эффектов на промежуточном этапе, а результаты объединяются в качестве последнего этапа. То есть Вы можете разбить на слова и / или список строк.

Вот как работает map-lower (и ваш случай не имеет значения, что все это происходит на одной машине).

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

boolean [] stringContainsWord (List<String> strings, String word);

Этот метод будет выполняться параллельно.

В этом случае логический массив будет иметь значение true для каждого индекса (списка), соответствующего данному слову.

и ваш редуктор (работает после завершения всех картографов):

List<String> getMatchingList(List<String>, List<boolean[]> mapperResults);

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

Вы можете дополнительно распараллелить задачу, разделив ваш список строк и запустив p-потоки для каждого слова, и каждый поток будет искать подмножество вашего списка Strings, так что входной список для вашего преобразователя равен 1 / р элементы общего списка.

-

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

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

(Обратите внимание, что вы все еще можете комбинировать первоначальный подход с этим.)

Answer 5

Что вам нужно, это Lucene

Answer 6

из идеи Эйспенсера, я соединил это

// Build the dictionary/data structure 
// O( [average split length]*n )
public static Dictionary<String,List<int>> BuildDictionary(String[] data)
{
    String[] temp;
    Dictionary<String,List<int>> dict = new Dictionary<String,List<int>>();
    for(int i = 0; i < data.length; i++)
    {
        temp = data[i].split(" ");
        for(int j = 0; j < temp.length; j ++)
        {
            if(dict.get(temp[j]) == null)
                dict.put(temp[j],new List<int>());

            dict.get(temp[j]).add(i);
        }
    }

    return dict;
}

// find all the matches
// O( [average number of matches per key]*[input split length])
public static List<int> FindMatches(String input, Dictionary<String,List<int> dict)
{
    String[] temp = input.split(" ");
    List<int> ret = new List<int>();

    for(int i = 0; i < temp.length; i++)
    {
        if(dict.get(temp[i]) == null)
            continue; // no match

        // read the match into the return list, ignore copies
        List<int> match = dict.get(temp[i]);
        for(int j = 0; j < match.count(); j++)
            if(!ret.contains(match.get(i))
                ret.add(match.get(i));
    }

    return ret;
}

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

Этот поиск чувствителен к регистру, но вы можете так же легко использовать toUpper или toLower, чтобы изменить его.

Answer 7

Этот код работает. Не знаю, достаточно ли это эффективно для вас:

    String[] dict = "foo bar".split(" ");

    String[] array = new String[] { "foo", "baz", "bar", "blah", "foo bar",
            "foo baz" };

    loop: for (String s : array) {
        String[] a = s.split(" ");

        for (String sample : dict)
            for (String s1 : a)
                if (sample.equals(s1)) {
                    System.out.println(s);
                    continue loop;
                }
    }