Ответ 1
Наблюдение за ключами
Мы можем использовать тот факт, что два слова в запросе могут совпадать с одним словом во фразе, только если одно слово запроса является префиксом другого слова запроса (или если оно одинаково). Поэтому, если мы обрабатываем слова запроса в нисходящем лексикографическом порядке (префиксы приходят после их "сверхслов" ), мы можем безопасно удалять слова из фраз в первом совпадении. Таким образом, мы не имели возможности сопоставить одно и то же слово фразы дважды. Как я уже сказал, это безопасно, потому что префиксы соответствуют superset фразовых слов, которые могут соответствовать их "суперсловам", а пара слов запроса, где один не является префиксом другого, всегда соответствует disjoint набор слов фразы.
Нам не нужно удалять слова из фраз или "физически", мы можем сделать это "практически".
Реализация алгоритма
var PhraseSearch = function () {
var Trie = function () {
this.phraseWordCount = {};
this.children = {};
};
Trie.prototype.addPhraseWord = function (phrase, word) {
if (word !== '') {
var first = word.charAt(0);
if (!this.children.hasOwnProperty(first)) {
this.children[first] = new Trie();
}
var rest = word.substring(1);
this.children[first].addPhraseWord(phrase, rest);
}
if (!this.phraseWordCount.hasOwnProperty(phrase)) {
this.phraseWordCount[phrase] = 0;
}
this.phraseWordCount[phrase]++;
};
Trie.prototype.getPhraseWordCount = function (prefix) {
if (prefix !== '') {
var first = prefix.charAt(0);
if (this.children.hasOwnProperty(first)) {
var rest = prefix.substring(1);
return this.children[first].getPhraseWordCount(rest);
} else {
return {};
}
} else {
return this.phraseWordCount;
}
}
this.trie = new Trie();
}
PhraseSearch.prototype.addPhrase = function (phrase) {
var words = phrase.trim().toLowerCase().split(/\s+/);
words.forEach(function (word) {
this.trie.addPhraseWord(phrase, word);
}, this);
}
PhraseSearch.prototype.search = function (query) {
var answer = {};
var phraseWordCount = this.trie.getPhraseWordCount('');
for (var phrase in phraseWordCount) {
if (phraseWordCount.hasOwnProperty(phrase)) {
answer[phrase] = true;
}
}
var prefixes = query.trim().toLowerCase().split(/\s+/);
prefixes.sort();
prefixes.reverse();
var prevPrefix = '';
var superprefixCount = 0;
prefixes.forEach(function (prefix) {
if (prevPrefix.indexOf(prefix) !== 0) {
superprefixCount = 0;
}
phraseWordCount = this.trie.getPhraseWordCount(prefix);
function phraseMatchedWordCount(phrase) {
return phraseWordCount.hasOwnProperty(phrase) ? phraseWordCount[phrase] - superprefixCount : 0;
}
for (var phrase in answer) {
if (answer.hasOwnProperty(phrase) && phraseMatchedWordCount(phrase) < 1) {
delete answer[phrase];
}
}
prevPrefix = prefix;
superprefixCount++;
}, this);
return Object.keys(answer);
}
function test() {
var phraseSearch = new PhraseSearch();
var phrases = [
'Stack Overflow',
'Math Overflow',
'Super User',
'Webmasters',
'Electrical Engineering',
'Programming Jokes',
'Programming Puzzles',
'Geographic Information Systems'
];
phrases.forEach(phraseSearch.addPhrase, phraseSearch);
var queries = {
's': 'Stack Overflow, Super User, Geographic Information Systems',
'web': 'Webmasters',
'over': 'Stack Overflow, Math Overflow',
'super u': 'Super User',
'user s': 'Super User',
'e e': 'Electrical Engineering',
'p': 'Programming Jokes, Programming Puzzles',
'p p': 'Programming Puzzles'
};
for(var query in queries) {
if (queries.hasOwnProperty(query)) {
var expected = queries[query];
var actual = phraseSearch.search(query).join(', ');
console.log('query: ' + query);
console.log('expected: ' + expected);
console.log('actual: ' + actual);
}
}
}
Здесь можно проверить этот код: http://ideone.com/RJgj6p
Возможные оптимизации
-
Сохранение количества слов фразы в каждом trie node - это не очень память эффективный. Но, реализуя сжатый trie, можно уменьшите сложность памяти наихудшего случая до O (n m), там n является количество разных слов во всех фразах, а m - общее количество количество фраз.
-
Для простоты я инициализирую
answer, добавив все фразы. Но более эффективный подход к времени - инициализироватьanswerпутем добавления фразы, соответствующие слову запроса, соответствующему наименьшему числу фразы. Затем пересекаются с фразами соответствия слова запроса второе наименьшее количество фраз. И так далее...
Соответствующие отличия от Реализация Ссылка в вопросе
- В trie node Я храню не только ссылки на фразу (ids), которые соответствуют подтипу, но и количество совпадающих слов в этих фразах. Таким образом, результатом совпадения являются не только совпадающие фразовые ссылки, но и количество совпадающих слов в этих фразах.
- Я обрабатываю слова запроса в нисходящем лексикографическом порядке.
- Я вычитаю количество суперпрефиксов (слова запроса, из которых текущее слово запроса является префиксом) из текущих результатов совпадения (с использованием переменной
superprefixCount), а фраза считается совпадающей с текущим словом запроса только тогда, когда результат число совпадающих слов в нем больше нуля. Как и в исходной реализации, конечным результатом является пересечение согласованных фраз.
Как можно видеть, изменения минимальны, а асимптотические сложности (как время, так и память) не изменяются.
