Cet article décrit l'algorithme de segmentation des mots d'appariement bidirectionnel implémenté par Java. Partagez-le pour votre référence, comme suit:
Plusieurs algorithmes de segmentation des mots populaires sont: la méthode de segmentation des mots basée sur la correspondance des chaînes, la méthode de segmentation des mots basée sur la compréhension et la méthode de segmentation des mots basée sur les statistiques. Cet article utilise la méthode de correspondance de chaînes.
Participle de correspondance maximum avant:
Cet algorithme est mis en œuvre sur la base du dictionnaire de participation Word, qui effectue une correspondance de segmentation à partir du côté gauche de la chaîne. Si le dictionnaire existe, il renvoie le mot divisé et coupe le mot de la chaîne précédente et boucles à couper jusqu'à ce que la taille de la chaîne soit 0.
Par exemple: STR = "Nous sommes tous des étudiants de la School of Information Engineering, Northwest A&F University.", (Supposons que nous définissons la longueur maximale de coupe max = 8, c'est-à-dire huit caractères chinois)
1. Définissez le mot longueur de participe len = max, retirez les caractères len du mot gauche = "Nous sommes tous l'agriculture et la foresterie du Nord-Ouest" et correspondent à un mot dans le dictionnaire;
2. S'il n'y a pas de mot dans le dictionnaire, supprimez le dernier caractère et affectez-le au mot, et la valeur Len est réduite de 1;
3. Répétez l'étape 2 jusqu'à ce que le mot se trouve dans le dictionnaire ou len = 1, quittez la boucle;
4. Coupez les mots divisés de STR et répétez les étapes 1, 2 et 3 jusqu'à ce que STR soit décomposé.
Participle de correspondance maximum inversé:
Comme l'algorithme de segmentation des mots avant, il commence simplement du côté droit de la chaîne jusqu'à ce que la longueur de la chaîne soit 0. Je n'entrerai pas dans les détails ici.
Participe assorti à double sens:
Cette méthode consiste à faire de l'ambiguïté participe pour segmenter l'ambiguïté sur la base du participe avant et du participe inversé. Proposer la mise en œuvre de "l'algorithme mangeur de serpents". La chaîne pour effectuer la segmentation des mots est la nourriture. Il y a 2 serpents gourmands, on mange de gauche à droite; l'autre mange de droite à gauche. Tant que les résultats du participe gauche et droit sont ambigus, les deux serpents le mordront. La chaîne que le serpent mange devient participe. S'il y a toujours une ambiguïté entre les participes gauche et droit, les deux serpents continueront de manger. Lorsque deux serpents mangent l'intersection entre les cordes, il n'y aura certainement pas d'ambiguïté. À l'heure actuelle, le participe du ventre de serpent gourmand à gauche, il n'y a pas d'ambiguïté au milieu, et le participe du ventre de serpent gourmand à droite, dont trois sont le participe final.
Cet article doit diviser l'ensemble du paragraphe en mots. Tout d'abord, le paragraphe est divisé en phrases en fonction des marques de ponctuation, puis chaque phrase est sortie pour diviser le mot.
Package Cn.nwsuaf.spilt; Importer java.io.bufferedeader; import java.io.fileReader; import java.io.ioexception; import java.util.arraylist; import java.util.hashmap; algorithme de segmentation des mots de correspondance maximale bidirectionnelle avant et inversé * @author liu yonglang * * / classe publique Wordspilt {/ ** * Dictionnaire de segmentation des mots de stockage * / map privé <chaîne, entier> map = new hashmap <string, entier> (); / ** * La longueur de coupe de mot maximale est de cinq caractères chinois * / private int max_length = 5; / ** * Lisez le mot Dictionary de participe dans la méthode de construction et stockez-le dans la carte * * @throws ioException * / public wordspilt () lève ioException {BuffereDReader br = new BufferedReader (new FileReader ("src / dict.txt")); Chaîne line = null; while ((line = br.readline ())! = null) {line = line.trim (); map.put (ligne, 0); } br.close (); } / ** * Définissez la longueur de coupe du mot maximum * * @param max * Longueur de coupe de mot maximale * / public void setmaxLength (int max) {this.max_length = max; } / ** * Obtenez la longueur de coupe de mot maximale actuelle, la valeur par défaut est 5 (5 caractères chinois) * * @return Longueur de coupe de mot maximale actuelle * / public int getMaxLength () {return this.max_length; } / ** * Algorithme de coupe de mot correspondant maximum * * @param SPILTSTR * String à diviser * @param LeftTORGH * La direction de tranchage, true est de gauche à droite, false est la chaîne divisée de droite à gauche * @return * / si la chaîne de tranchent (String Spiltstr, Retournet If (SpiltsSter) {//) est vide, Retour If (SpiltsSter) retourner null; // Stockez la liste de chaîne Split Split Positive <string> Leftwords = new ArrayList <string> (); // Stockez la liste de chaîne Split Split négative <string> droitewords = new ArrayList <string> (); // chaîne pour trancher word de chaîne = null; // prenez la longueur du mot, initialisez à la valeur maximale int wordLength = max_length; // est dans la position actuelle de la chaîne int position = 0; // La longueur de la chaîne a été traitée int length = 0; // Retirez les espaces supplémentaires dans la chaîne SpilTStr = Spiltstr.trim (). RempaceALL ("// S +", ""); // Lorsque la chaîne à trancher n'est pas tranchée, segmentation en boucle tandis que (longueur <spiltstr.length ()) {// Si la longueur de la chaîne qui n'a pas été tranchée est inférieure à la valeur maximale, laissez la longueur du mot égal à la longueur du mot lui-même if (spiltstr.length () - longueur <max_length) wordLength = SpiltStr.Length () - longueur; // Sinon, prenez la valeur par défaut else wordLength = max_length; // S'il s'agit d'une correspondance maximale avant, commencez à couper à partir de la position de SpilTtr if (LeftToRight) {position = longueur; word = spiltstr.substring (position, position + wordLength); } // S'il s'agit d'une correspondance maximale inverse, commencez à couper à partir de la fin de SPILTSTR ELSE {position = spiltstr.length () - longueur; word = spiltstr.substring (position - wordLength, position); } // Commencez à couper la chaîne de la longueur spécifiée de la position actuelle // word = spiltstr.substring (position, position + wordLength); // S'il n'y a pas de chaîne coupée dans le mot participe Dictionary, jetez un caractère while (! Map.containsKey (word)) {// Si c'est un seul mot, quittez la boucle if (word.length () == 1) {// Si c'est une lettre ou un numéro, divisez les lettres ou chiffres continu Loop pour additionner les caractères continus suivants if (LeftToright) {for (int i = spiltstr.indexof (word, position) + 1; i <spilttr .length (); i ++) {if ((spiltstr.charat (i)> = '0' && spiltstr.charat (i) <= '9') || (Spiltstr.Charat (i) <= '9') || ((spiltstr.charat (i) <= '9') || (Spiltstr.Charat (A) Spiltstr .Charat (i) <= 'z') || (spiltstr.charat (i)> = 'a' && spiltstr .charat (i) <= 'z')) {word + = spiltstr.charat (i); } else se briser; }} else {// S'il s'agit d'une correspondance inverse, additionnez et retournez les nombres continus et les caractères alphabétiques avant la position actuelle pour (int i = spiltstr.indexof (mot, position - 1) - 1; i> = 0; i--) {if ((spiltstr.charat (i)> = '0' && SPILTSTR.Charat (i) <= '9') > = 'A' && spiltstr.charat (i) <= 'z') || (spiltstr.charat (i)> = 'a' && spiltstr.charat (i) <= 'z')) {word + = spiltstr.charat (i); if (i == 0) {stringBuffer sb = new StringBuffer (word); word = sb.reverse (). toString (); }} else {// Flip Operation StringBuffer SB = new StringBuffer (Word); word = sb.reverse (). toString (); casser; } } } } casser; } // S'il s'agit d'une correspondance maximale avant, jetez le dernier caractère if (LeftToright) word = word.substring (0, word.length () - 1); // Sinon, jetez le premier caractère else word = word.substring (1); } // Enregistrez la chaîne divisée dans la table spécifiée if (LeftToRight) Leftwords.Add (Word); else Rightwords.Add (Word); // les chaînes traitées ajoutent la longueur + = word.length (); } // S'il s'agit d'une correspondance maximale inverse, ajustez la chaîne dans la table pour transmettre si (! LeftToRight) {for (int i = droite.Size () - 1; i> = 0; i--) {Leftwords.Add (droite.Get (i)); }} // Renvoie le résultat de découpage Retour des mots à gauche; } / ** * Déterminez si les deux ensembles sont égaux * * @param list1 * set 1 * @param list2 * set 2 * @return return true if equal, sinon false * / public boolean isEqual (list <string> list1, list <string> list2) {if (list1.isempty () && list2.iSempty ()) return false; if (list1.size ()! = list2.size ()) return false; pour (int i = 0; i <list1.size (); i ++) {if (! list1.get (i) .equals (list2.get (i))) return false; } return true; } / ** * Fonction d'ambiguïté de participe discriminant * * @param inputStr * String à diviser * @return partition Résultat * / public list <string> resultword (String inputStr) {// partition Result list <string> result = new ArrayList <string> (); // "Left Snake" Liste de résultats de participe <string> resultLeft = new ArrayList <string> (); // "Snake moyen" (pièce divergente) Liste des résultats du participe <string> resultMiddle = new ArrayList <string> (); // "Snake droit" Liste des résultats de participe <string> resultRight = new ArrayList <string> (); // Faire la liste des résultats de la segmentation des mots correspondant maximum <string> Left = new ArrayList <string> (); // Liste des résultats de la segmentation des mots correspondante inverse <string> droite = new ArrayList <string> (); Left = Spilled (Inputstr, true); /*System.out.println(" Résultat du participe vers l'avant: "); for (String String: Left) {System.out.print (String + "/"); } System.out.println ("/ n Résultat du participe inverse:"); * / droite = Spilled (inputstr, false); / * for (String String: droite) {System.out.print (String + "/"); } System.out.println ("/ nboth-way word participe Résultat:"); * / // // déterminer si le mot épissage du mot de participe aux deux extrémités s'est croisé au milieu de la chaîne d'entrée. Tant qu'il n'y a pas d'intersection, il continue de boucler tandis que (Left.get (0) .length () + droite.get (droite.size () - 1) .length () <inputStr .length ()) {// Si les résultats du mot avant et inversé sont égaux, alors le résultat avant sautra de la boucle si (est égal (gauche, droite)) {résultat casser; } // Si les résultats du participe de mot avant et inversé sont différents, alors celui avec le plus petit nombre de participes est pris, et il n'est pas nécessaire de boucler si (Left.size ()! = Droite.size ()) {resultMiddle = Left.size () <droite.Size ()? gauche: droite; casser; } // Si les conditions ci-dessus ne sont pas remplies, implémentez l'algorithme "Snake" // Let "Left Greedy Snake" mangez le premier mot du résultat de mot avant résultat. // Laissez le "serpent gourmand droit" mange le dernier mot du mot inverse du résultat de participe resultright.add (droite.get (droite.size () - 1)); // Retirez les mots mangés par "Snake" inputstr = inputstr.substring (Left.get (0) .length ()); inputstr = inputstr.substring (0, inputstr.length () - droite.get (droite.size () - 1) .length ()); // Nettoyez les résultats de la segmentation des mots positifs et inversés précédents pour empêcher l'interférence gauche.Clear (); droite.clear (); // Démarrez le participe pour les chaînes non mangées à gauche = Spilled (Inputstr, true); Right = Spilled (Inputstr, false); } // La fin de la boucle signifie que le participe n'est pas ambigu, ou le "serpent gourmand" mange des deux extrémités à l'intersection // Si c'est le mot participe à l'intersection, le jugement suivant doit être porté: // Si l'intersection moyenne se débarrasse de la longueur totale de la chaîne, prenez directement la longueur de la participation dans la direction inverse> Entrer la longueur totale de la chaîne, prenez directement la pose de la participation dans la direction inverse> Entrez la longueur totale de la chaîne, prenez directement la pose de la participation dans la direction inverse> Entrez la longueur totale de la chaîne, prenez directement la positives de la participation dans la direction inverse> Entrez la longueur totale de la chaîne, prenez directement le Positi (Left.get (0) .length () + droite.get (droite.size () - 1) .length ()> inputstr .length ()) resultMiddle = gauche; // Si l'intersection moyenne se croit, elle prend simplement la nourriture et qu'il n'y a pas de chevauchement: // le premier participe dans la direction avant + la longueur du dernier participe dans la direction inverse = Entrez la longueur totale de la chaîne, alors la direction avant et inverse peut être orthographié if (left.get (0) .length () + droite.) resultMiddle.add (Left.get (0)); resultMiddle.add (droite.get (droite.size () - 1)); } // Ajouter un résultat de participe non ambigu au résultat final pour (String String: resultEft) {result.add (string); } pour (String String: resultMiddle) {result.add (string); } // Le participe stocké dans "Snake gourmand droit" doit être ajusté à l'avant pour (int i = resultRight.size () - 1; i> = 0; i--) {result.add (resultTright.get (i)); } Retour Résultat; } / ** * Divisez un paragraphe en plusieurs phrases et effectuez une segmentation des mots séparément * * @param inputstrt * Un paragraphe à diviser * @return en résultat de ce paragraphe * / public list <string> Resultspilt (String inputstr) {// utilisé pour stocker la liste de résultats de la segmentation des mots finaux <String> result = new ArrayList <String> (); // Si la ponctuation est rencontrée, elle sera divisée en plusieurs phrases String regex = "[,.;!?]"; String [] st = inputstr.split (regex); // Ajouter le résultat du participe de chaque phrase au résultat du participe final pour (String stri: st) {list <string> list = resultword (stri); result.addall (liste); } Retour Résultat; } public static void main (String [] args) {// Exemple: Venez voir si le prix des maisons est cher? Tableau de tennis de tennis Entrée du scanner = nouveau scanner (System.in); String str = input.nextline (); Wordspilt wordspilt = null; essayez {wordspilt = new wordspilt (); } catch (ioException e) {e.printStackTrace (); } List <string> list = wordspilt.resultword (str); for (String String: list) {System.out.print (String + "/"); }}}Le src / dict.txt est un fichier de dictionnaire, et les paramètres sont les suivants:
Bienvenue sur Wulin.com Script Download Script Tutorial Matériel Télécharger
Les résultats de l'opération sont les suivants:
Pour plus d'informations sur les algorithmes Java, les lecteurs qui sont intéressés par ce site peuvent afficher les sujets: "Structure de données Java et tutoriel d'algorithme", "Résumé des conseils de nœud de Dom Operation Java", "Résumé du fichier Java et des conseils d'opération de répertoire" et "Résumé des conseils d'opération Java Cache"
J'espère que cet article sera utile à la programmation Java de tous.