Disons que nous avons des chaînes comme celle-ci:

Tommy is a very good child
Tommy has a very wonderful child
Tommy loves his very child

Je veux extraire les mots communs des 3 chaînes ci-dessus comme:

Tommy*very*child 

Comment suis-je censé faire ça? Merci.

0
Bill Randerson 23 déc. 2015 à 05:31

3 réponses

Meilleure réponse

Vous pouvez utiliser la structure de données appelée inverted index

Vous attribuez d'abord un entier unique à chacune de vos chaînes d'entrée. Ensuite, l'idée est que pour chaque mot dans les chaînes d'entrée, vous voulez calculer une liste d'entiers indiquant les chaînes dans lesquelles le mot apparaît. Notez que vous pouvez facilement le faire en traitant simplement toutes les chaînes d'entrée. Dans votre cas, afin d'obtenir des mots apparaissant dans toutes les chaînes, vous pouvez générer des mots dont la liste d'occurrences a le même nombre d'entrées que le nombre de chaînes dans l'entrée.

Pour plus de détails, veuillez vous référer ici:

https://en.wikipedia.org/wiki/Inverted_index

2
pkacprzak 23 déc. 2015 à 11:06

EDIT Je viens de réaliser le commentaire de @ Joce, et j'ai mis ma réponse en JavaScript. Mais il peut facilement être adapté à d'autres langues. S'il ne s'agit pas de JavaScript, traitez-le comme un pseudocode.

MODIFIER 2 Whoa! Cela a très bien fonctionné lors de mon premier essai! Voir l'exemple de travail sur JSFiddle.net.

Cela peut être une réponse de script très volumineuse, mais voici:

Étant donné les phrases originales sous forme de tableaux de chaînes:

var sentences = [
    "Tommy is a very good child",
    "Tommy has a very wonderful child",
    "Tommy loves his very child"
];

Vous pouvez essayer de créer un tableau de mots à partir de chaque tableau, en le stockant dans un tableau multidimensionnel.

var split = [];
for(var i = 0; i < sentences.length; i++) {
    split[i] = sentences[i].split(" ");
}

Vous pouvez également supprimer les doublons de mots ici, mais je ne sais pas comment le faire sur place, mais vous pourriez probablement obtenir un algorithme simple pour le faire. À moins que vous n'autorisiez les phrases de mots en double, bien sûr.

Ensuite, vous pouvez créer un autre tableau avec des mots identiques et le remplir comme ceci:

var same = [];
for(var i = 0; i < split.length; i++) {             // loop through sentences
    for(var j = 0; j < split[i].length; j++) {      // go through each sentence for new words
        if(same.indexOf(split[i][j]) <= -1) {       // if not already found
            var inAll = true;
            for(var k = 0; k < split.length; k++) { // check if in every sentence
                if(k == i) continue;
                if(split[k].indexOf(split[i][j]) <= -1) inAll = false; // if not found, make `inAll` false
            }
            if(inAll) same.push(split[i][j]);       // if found in all other sentences, add to array `same`
        }
    }
}

Désolé, c'est une réponse si compliquée, mais elle devrait montrer la logique derrière l'algorithme. Si vous le souhaitez, essayez de changer autour des chaînes sur JSFiddle.

1
Jonathan Lam 23 déc. 2015 à 02:55

Pour faire simple, j'utiliserai lodash ici:

var a = 'Hello world'.split(' ');
var b = 'Hello again world!'.split(' ');
var c = 'Hello tomorrow'.split(' ');

var commonWords = _.union(a, b, c);
// => ['Hello']

J'ai utilisé lodash simplement parce qu'il fournit une méthode succincte pour ce que, en réalité, vous essayez de faire, qui est une union , basée (par exemple) sur des délimiteurs et des transformations.

Une union est indépendante de la langue: l'algorithme que vous utilisez pour implémenter l'union différera quelque peu en fonction de la langue que vous choisissez.

Vous pouvez l'utiliser dans une fonction, où vous définissez des délimiteurs (par exemple, est-ce que je sépare en un espace?) Et des transformations (par exemple, les mots doivent-ils être en majuscules pour correspondre?)

2
Josh Beam 23 déc. 2015 à 02:57