Статьи

Создание локального индекса полнотекстового поиска

Сентябрь 11, 2018

Одна проблема с UrzaGatherer связана с поиском. Как вы, наверное, знаете, у меня есть огромный список карточек, сохраненных локально, и мое приложение позволяет пользователю искать определенные карточки, используя часть их имени. Но просмотр более 20 000 карточек с помощью текстового поиска может быть очень дорогим, в основном на недорогом оборудовании.

В настоящее время код выглядит примерно так:

cards = UrzaGatherer.CardsList.createFiltered(queryFunction)

Я использую объект WinJS.Binding.List для создания отфильтрованного представления, используя мой шаблон поиска.

Функция фильтра использует простую функцию indexOf :

var queryFunction = function (card) {
    if (card.name.indexOf(textSearch) !== -1) {
        return true;
    }

    return false;
};

Но очевидно, что может потребоваться время, чтобы выполнить поиск с использованием этого решения. Сложность почти равна O (n * m), что можно упростить до O (n²) (где n — количество карточек, а m — средняя длина названия карточек).

Итак, вопрос: как я могу оптимизировать свой поиск?

Построение дерева полнотекстового поиска

Одно решение можно найти с помощью дерева поиска. Такая структура позволяет выполнять поиск со сложностью O (n), где n — средняя длина имени карты.

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

Например, если мы используем строку «urza», дерево будет выглядеть так:

образ

Листья содержат идентификатор связанной карты.

Если я добавлю новую строку, например «Пицца», к моему предыдущему дереву, получится следующее дерево:

образ

Обратите внимание, что некоторые листы могут содержать много карт (например, для «ZA» и «A»)

Связанный код довольно прост:

var root;

var processString = function(string, offset, node, object) {
    if (!string || offset == string.length) {
        return;
    }

    var currentNode = node;

    for (var index = offset; index < string.length; index++) {
        var c = string[index];

        if (currentNode[c] === undefined) {
            currentNode[c] = {};
        }

        currentNode = currentNode[c];
    }

    if (currentNode.ref == undefined)
        currentNode.ref = [];

    if (currentNode.ref.indexOf(object.id) == -1) {
        currentNode.ref.push(object.id);
    }

    processString(string, offset + 1, root, object);
};

var addString = function (string, object) {
    if (!string)
        return;
    
    if (!root)
        root = { };

    processString(string.toLowerCase(), 0, root, object);
};

Поиск с использованием полнотекстового дерева поиска

Функция поиска — это простой обход дерева:

var concatArray = function (source, data) {
    for (var index = 0; index < data.length; index++) {
        source[data[index]] = {};
    }
};

var gatherResults = function (node, results) {
    for (var prop in node) {
        if (prop == "ref")
            concatArray(results, node[prop]);
        else
            gatherResults(node[prop], results);
    }
};

var searchString = function (string) {
    var currentNode = root;

    for (var index = 0; index < string.length; index++) {
        var c = string[index];

        if (currentNode[c] === undefined)
            return {};

        currentNode = currentNode[c];
    }

    var results = {};
    gatherResults(currentNode, results);

    return results;
};

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

Вы также можете легко сохранить дерево с помощью JSON:

var persistIndex = function(filename) {
    var data = JSON.stringify(root);
    return Windows.Storage.ApplicationData.current.localFolder.createFileAsync(filename, 
Windows.Storage.CreationCollisionOption.replaceExisting)
        .then(function (file) {
        return Windows.Storage.FileIO.writeTextAsync(file, data);
    });
};

var resetIndex = function() {
    root = undefined;
};

var loadIndex = function(filename) {
    return Windows.ApplicationModel.Package.current.installedLocation.getFolderAsync("data")
        .then(function(localFolder) {
        return localFolder.getFileAsync(filename).then(function(file) {
            return Windows.Storage.FileIO.readTextAsync(file).then(function(data) {
                if (data) {
                    root = JSON.parse(data);
                }
            });
        });
    });
};

Например, полный индекс для моих 20 000 карт весит 6 Мб .

Полученные результаты

Пылающий быстро! Ничего больше Sourire. Используя мое дерево поиска, я могу выполнить поиск по всей коллекции менее чем за 300 мс, где раньше для того же результата может потребоваться до 20 с.

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

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

43
Share: