Javascript / JQuery Найти текстовые дубликаты

Question

Как бы вы подошли к поиску дубликатов в текстовом документе. Дубликаты могут быть набором последовательных слов или предложений. Приговор не обязательно заканчивается точкой. скажем, страница содержит документ из 200 строк, из которых 2 предложения идентичны, мы хотим выделить эти 2 предложения как дубликаты при нажатии кнопки «Проверить дубликат».

Answer 1

Интересный вопрос - вот идея о том, как бы я это сделал, вероятно: http://jsfiddle.net/SaQAs/1/ - Не оптимизировано так или иначе!

var text = $('p').text(),
    words = text.split(' '),
    sortedWords = words.slice(0).sort(),
    duplicateWords = [],
    sentences = text.split('.'),
    sortedSentences = sentences.slice(0).sort(),
    duplicateSentences = [];


for (var i=0; i<sortedWords.length-1; i++) {
    if (sortedWords[i+1] == sortedWords[i]) {
        duplicateWords.push(sortedWords[i]);
    }
}
duplicateWords = $.unique(duplicateWords);

for (var i=0; i<sortedSentences.length-1; i++) {
    if (sortedSentences[i+1] == sortedSentences[i]) {
        duplicateSentences.push(sortedSentences[i]);
    }
}
duplicateSentences = $.unique(duplicateSentences);

$('a.words').click(function(){
    var highlighted = $.map(words, function(word){
        if ($.inArray(word, duplicateWords) > -1)
            return '<span class="duplicate">' + word + '</span>';
        else return word;
    });
    $('p').html(highlighted.join(' '));
    return false;
});

$('a.sentences').click(function(){
    var highlighted = $.map(sentences, function(sentence){
        if ($.inArray(sentence, duplicateSentences) > -1)
            return '<span class="duplicate">' + sentence + '</span>';
        else return sentence;
    });
    $('p').html(highlighted.join('.'));
    return false;
});

---

Обновление 1

Этот находит последовательности идентичных слов: http://jsfiddle.net/YQdk5/1/ Отсюда не должно быть трудно, например. игнорируйте любые знаки препинания в конце фрагментов при сравнении - вам просто нужно написать собственную версию inArray метода.

var text = $('p').text(),
    words = text.split(' '),
    sortedWords = words.slice(0).sort(),
    duplicateWords = []
    highlighted = [];

for (var i=0; i<sortedWords.length-1; i++) {
    if (sortedWords[i+1] == sortedWords[i]) {
        duplicateWords.push(sortedWords[i]);
    }
}
duplicateWords = $.unique(duplicateWords);

for (var j=0, m=[]; j<words.length; j++) {
    m.push($.inArray(words[j], duplicateWords) > -1);
    if (!m[j] && m[j-1]) 
        highlighted.push('</span>');
    else if (m[j] && !m[j-1])
        highlighted.push('<span class="duplicate">');
    highlighted.push(words[j]);
}

$('p').html(highlighted.join(' '));

Обновление 2

Мое регулярное выражение слабое, но эта (довольно грязная!) Версия, кажется, работает нормально: http://jsfiddle.net/YQdk5/2/ - Я почти уверен, что может быть лучший способ сделать это, но сейчас я Я должен оставить это в покое! : D - Удачи!

Обновление 3

Думая об этом, я не думаю, что код из предыдущего обновления будет хорошим. Вот почему я удалил это. Вы все еще можете найти его здесь: http://jsfiddle.net/YQdk5/2/ Суть в том, чтобы использовать регулярное выражение для сопоставления слов, что-то вроде:

/^word(\.?)$/

Answer 2

Вот решение, использующее суффиксное дерево:

function SuffixTree(text) {
    var regex = /\b\w+/g;
    var words = text.match(regex);
    var wave = [];
    var words_l = words.length;
    if (words_l == 0) return false;
    this.tree = this.node("", false);
    for (var i = 0; i < words_l; ++i) {
        var x = words[i] + "_";
        wave.push(this.tree);
        var wave_l = wave.length;
        for (var j = 0; j < wave_l; ++j) {
            var y = wave[j];
            if (typeof y[x] != 'undefined') y[x].count++;
            else y[x] = this.node(words[i], y);
            wave[j] = y[x];
        }
    }
}

SuffixTree.prototype = {
    dummy: {count: 1},

    node: function(word, num, parent) {
        return {
            count: 1,
            word: word,
            parent: parent
        };
    },

    duplicates: function(h) {
        this.dups = [];
        this.bypass(this.tree, h, 0);
        var l = this.dups.length;
        this.dups.sort(function(d1, d2) { return d1.depth > d2.depth ? 1 : -1; });
        for (var i = 0; i < l; ++i) {
            var d = this.dups[i];
            this.dups[i] = { s: " " + this.sentence(d.a) + " ", depth: d.depth, count: d.a.count };
        }
        for (var i = 0; i < l; ++i) {
            var d = this.dups[i];
            console.log(i, d.s);
        }
        for (var i = 0; i < l; ++i) {
            var d = this.dups[i];
            var fl = true;
            for (var j = i + 1; j < l; ++j) {
                if (this.dups[j].s.indexOf(d.s) != -1) fl = false;
            }
            if (fl) h(d.s.substr(1, d.s.length - 2), d.count);
        }
    },

    bypass: function(a, h, depth) {
        if (a.constructor != Object) return;
        var fl = true;
        for (var i in a) {
            if (i == 'parent') continue;
            var b = a[i];
            if (b.count == a.count) fl = false;
            this.bypass(b, h, depth + 1);
        }
        if (fl && a.count > 1) {
            this.dups.push({ a: a, depth: depth });
        }
    },

    sentence: function(a) {
        var s = a.word;
        while (a = a.parent) {
            s = a.word + " " + s;
        }
        return s;
    }
};

var text = "This is a text with some duplicates: words, sentences of different length. For example here is a duplicate word. This sentence has some duplicates. But not all of us can find clones.";

var T = new SuffixTree(text);
var h = function(s, c) {
    document.write(s + "[" + c + "]<br/>");
};
T.duplicates(h);

1) Разделить входной текст на массив слов. 2) Постройте дерево суффиксов. 3) Найдите самые длинные суффиксы дерева. 4) Удалите предложения, содержащиеся в других (то есть удалите «есть», которое является частью «это есть»).

Вы можете изменить регулярное выражение для учета тегов html.

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

P.S. h - обратный вызов для найденных дубликатов.

Answer 3

Ваш javascript содержит ссылки на библиотеку javascript с именем jQuery.

Вы не включили это в свой HTML, и, таким образом, оно не будет выполнено. Вы можете включить его через jquery cdn

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