Este artículo describe el algoritmo de segmentación de palabras de correspondencia bidireccional implementado por Java. Compártelo para su referencia, como sigue:
Varios algoritmos populares de segmentación de palabras son: método de segmentación de palabras basado en la coincidencia de cadenas, el método de segmentación de palabras basado en la comprensión y el método de segmentación de palabras basado en estadísticas. Este artículo utiliza el método de coincidencia de cadenas.
Reenviar el participio máximo coincidente:
Este algoritmo se implementa en función del diccionario de participio de Word, que realiza una coincidencia de segmentación desde el lado izquierdo de la cadena. Si el diccionario existe, devuelve la palabra dividida y corta la palabra de la cadena anterior, y los bucles para cortar hasta que el tamaño de la cadena sea 0.
Por ejemplo: Str = "Todos somos estudiantes de la Escuela de Ingeniería de la Información, Noroeste de la Universidad de A&F". (Supongamos que definimos la longitud máxima de corte máx = 8, es decir, ocho caracteres chinos)
1. Defina la palabra longitud del participio len = max, elimine los caracteres del len de la palabra izquierda = "Todos somos agricultura del noroeste y silvicultura" y coinciden con la palabra en el diccionario;
2. Si no hay tal palabra en el diccionario, elimine el último carácter y asigna a Word, y el valor de LEN se reduce en 1;
3. Repita el paso 2 hasta que la palabra se encuentre en el diccionario o len = 1, salga del bucle;
4. Corta las palabras divididas del STR y repite los pasos 1, 2 y 3 hasta que STR se descomponga.
Participio de correspondencia máximo inverso:
Al igual que el algoritmo de segmentación de Word Forward, simplemente comienza desde el lado derecho de la cadena hasta que la longitud de la cadena sea 0. No entraré en detalles aquí.
Participio a juego de dos vías:
Este método es hacer un participio de ambigüedad para segmentar la ambigüedad sobre la base del participio hacia adelante y el participio inverso. Proponer la implementación del "Algoritmo de comer serpiente". La cadena para realizar la segmentación de palabras es la comida. Hay 2 serpientes glotón, una come de izquierda a derecha; El otro come de derecha a izquierda. Mientras los resultados del participio izquierdo y derecho sean ambiguos, las dos serpientes lo morderán. La cuerda que come la serpiente se convierte en participio. Si siempre hay ambigüedad entre los participios izquierdo y derecho, las dos serpientes seguirán comiendo. Cuando dos serpientes comen la intersección entre las cuerdas, definitivamente no habrá ambigüedad. En este momento, el participio en el codicioso abdomen de serpiente a la izquierda, no hay ambigüedad en el medio y el participio en el vientre de serpiente codiciosa a la derecha, tres de los cuales son el participio final.
Este artículo es dividir todo el párrafo en palabras. Primero, el párrafo se divide en oraciones basadas en signos de puntuación, y luego cada oración se emite para dividir la palabra.
paquete cn.nwsuaf.spilt; import java.io.bufferedReader; import java.io.filereader; import java.io.ioexception; import java.util.arrayList; import java.util.hashmap; import java.util.list; import java.util.map; import java.util. El algoritmo de segmentación de palabras máximo de combate máximo hacia adelante e inversa* @author liu yonglang**/public classpilt {/*** Diccionario de segmentación de palabras de almacenamiento*/Map privado <string, entero> map = new Hashmap <String, Integer> (); / *** La longitud máxima de corte de palabras es cinco caracteres chinos*/ private int max_length = 5; /** * Lea el diccionario de participio de la palabra en el método de construcción y guárdelo en el mapa * * @throws ioexception */public WordsPilt () lanza ioexception {BufferedReader br = new BufferedReader (new FileReader ("src/dict.txt"); Línea de cadena = nulo; while ((line = br.readline ())! = null) {line = line.trim (); map.put (línea, 0); } br.close (); } / *** Establezca la longitud máxima de corte de palabra** @param max* longitud máxima de corte de palabra* / public void setmaxLength (int max) {this.max_length = max; } / ** * Obtenga la longitud de corte de palabra máxima actual, el valor predeterminado es 5 (5 caracteres chinos) * * @return longitud de corte de palabra máxima actual * / public int getMaxLength () {return this.max_length; } /** * Maximum matching word cut algorithm* * @param spiltStr * String to be split* @param leftToRight * The slicing direction, true is from left to right, false is the string divided from right to left * @return */ public List<String> spilt(String spiltStr, boolean leftToRight) { // If the slicing string is empty, return empty if (spiltStr.isEmpty()) return null; // almacenar la lista de cadenas divididas positivas de coincidencia <String> LeftWords = new ArrayList <String> (); // Almacene la lista de cadenas divididas de correspondencia negativa <String> RightWords = new ArrayList <String> (); // cadena para cortar cadena word = null; // Tome la longitud de la palabra, inicialice al valor máximo int wordLength = max_length; // está en la posición actual de la cadena int posición = 0; // La longitud de la cadena se ha procesado int longitud = 0; // Retire los espacios adicionales en la cadena spilTStr = spiltstr.trim (). ReplaceAll ("// s+", ""); // Cuando la cadena que se corta no se corta, la segmentación de bucle, mientras que (longitud <spiltstr.length ()) {// si la longitud de la cadena que no ha sido cortada es menor que el valor máximo, deje que la longitud de la palabra sea igual a la longitud de la palabra misma if (spiltstr.length () - longitud <max_length) wordlength = spiltstr.length () - longitud; // de lo contrario, tome el valor predeterminado el más wordlength = max_length; // Si se trata de una coincidencia máxima delantera, comience a cortar desde la posición de SpilTstr if (LeftToRight) {position = longitud; word = spiltstr.substring (posición, posición + wordlength); } // Si se trata de una coincidencia máxima inversa, comience a cortar desde el extremo de SpilTstr Else {posicion = spiltstr.length () - longitud; word = spiltstr.substring (posición - Wordlength, posición); } // Comience a cortar la cadena de la longitud especificada de la posición actual // word = spilTstr.substring (posición, posición + WordLength); // Si no hay una cadena cortada en el diccionario de participio de la palabra, descarte un personaje mientras (! Map.containskey (word)) {// Si es una sola palabra, salga el bucle if (word.length () == 1 1) {// Si es una letra o número, divide las letras continuas o números juntos si (word.matches ("[a-za-z0-9]"))))) Agregue los caracteres continuos posteriores if (LeftToRight) {for (int i = spiltstr.indexof (word, posicion)+1; i <spiltstr .length (); i ++) {if ((spiltstr.charat (i)> = '0' && spiltstr.charat (i) <= '9') || (spiltstr.charat (i)> = 'a' a '&&&&&&&&&&&&&&&d) <= 'Z') || (spltstr.charat (i)> = 'a' && spltstr .charat (i) <= 'z')) {word += spiltstr.charat (i); } el más ruptura; }} else {// Si se trata de una coincidencia inversa, suministre y voltee los números continuos y los caracteres alfabéticos antes de la posición actual para (int i = spilTstr.IndexOf (word, posición - 1) - 1; i> = 0; i--) {if ((spiltstr.carat (i)> = '0' && spiltstr.charat (i) 'A' && Spltstr.Charat (i) <= 'Z') || if (i == 0) {StringBuffer sb = new StringBuffer (Word); word = sb.reverse (). toString (); }} else {// Flip Operation StringBuffer sb = new StringBuffer (Word); word = sb.reverse (). toString (); romper; } } } } romper; } // Si es una coincidencia máxima delantera, descarte el último carácter if (LeftToRight) word = word.substring (0, word.length () - 1); // De lo contrario, descarte el primer personaje más word = word.substring (1); } // Guardar la cadena dividida en la tabla especificada if (LeftToRight) LeftWords.Add (Word); else Rightwords.Add (palabra); // cadenas procesadas agregue longitud += word.length (); } // Si se trata de una coincidencia máxima inversa, ajuste la cadena en la tabla para reenviar if (! LeftToright) {for (int i = rightwords.size ()-1; i> = 0; i--) {LeftWords.add (rightwords.get (i)); }} // devuelve el resultado de corte return LeftWords; } / ** * Determine si los dos conjuntos son iguales * * @param list1 * set 1 * @param list2 * set 2 * @return return true Si igual, de lo contrario falso * / public boolean isequal (list <string> list1, list <string> list2) {if (list1.isEmpty () && list.isEmpty () return false; if (list1.size ()! = list2.size ()) return false; for (int i = 0; i <list1.size (); i ++) {if (! list1.get (i) .equals (list2.get (i))) return false; } return verdadero; } / *** Función de ambigüedad del participio discriminante** @param Inputstr* cadena para dividirse* @return Partition Result* / public List <String> Resultword (String InputStr) {// Partition Result List <String> Result = New ArrayList <String> (); // Lista de resultados del participio "Left Snake" <String> Resultleft = new ArrayList <String> (); // "Snake Medium" (parte divergente) Lista de resultados del participio <String> resultMiddle = new ArrayList <String> (); // Lista de resultados del participio "Right Snake" <String> resultright = new ArrayList <String> (); // Reenviar la lista máxima de resultados de segmentación de palabras coincidentes <String> Left = new ArrayList <String> (); // Lista de resultados de segmentación de palabras de coincidencia máxima inversa <String> Right = New ArrayList <String> (); Left = Spilled (InputStr, True); /*System.out.println("Forward Particle Resultado: "); for (cadena String: Left) {System.out.print (String + "/"); } System.out.println ("/n resultado del participio inverso:"); */ right = Spilled (inputStr, falso); /*for (cadena String: Right) {System.out.print (String + "/"); } System.out.println ("/ Nboth-Way Word Participle Resultado:");*/ // // Determinar si el empalme del participio de la palabra en ambos extremos se ha cruzado en el medio de la cadena de entrada. Mientras no haya intersección, se mantiene en bucle mientras (left.get (0) .Length () + right.get (derecho.size () - 1) .length () <inputStr .Length ()) {// Si los resultados del participio de la palabra reenviada e inversa son iguales, entonces el resultado del avance saltará del bucle si (es igual (izquierda, derecha))) romper; } // Si los resultados del participio de palabras hacia adelante e inversa son diferentes, entonces se toma el número más pequeño de participios, y no es necesario que se reduzcan si (izquierda.size ()! = Right.size ()) {resultMiddle = left.size () <derecho.size ()? Izquierda: derecha; romper; } // Si no se cumplen las condiciones anteriores, implementa el algoritmo de "serpiente" // deja que "serpiente codiciosa izquierda" coma la primera palabra del resultado del participio de la palabra delantera resultanteft.add (izquierda.get (0)); // Deje que "la serpiente codiciosa correcta" coma la última palabra del participio de la palabra inversa Resultright.Add (Right.get (Right.size () - 1)); // Eliminar las palabras comidas por "serpiente" inputstr = inputStr.substring (left.get (0) .length ()); inputStr = inputStr.substring (0, inputStr.length () - right.get (right.size () - 1) .length ()); // Limpiar los resultados anteriores de segmentación de palabras positivas e inversas para evitar interferencias a la izquierda. right.clear (); // Inicie el participio para las cadenas de desataje a la izquierda = Spilled (inputStr, true); right = Spilled (inputstr, falso); } // El final del bucle significa que el participio no es ambiguo, o la "serpiente codiciosa" come desde ambos extremos hasta la intersección // Si es el participio de la palabra en la intersección, el siguiente juicio debe hacerse: // Si la intersección media se superpone: // la longitud del primer participio + la longitud del último participio en la dirección inversa de la longitud total de la cuerda, directamente, la longitud del primer participio + la longitud del último participio en la dirección inversa de la cuerda, directamente, la longitud del primer participio + la longitud del último participio en la dirección inversa de la cadena, directamente, tome el positivo directamente el positivo. (izquierda.get (0) .length () + right.get (right.size () - 1) .length ()> inputStr .Length ()) resultMiddle = Left; // Si la intersección media se cruza, solo toma el alimento y no hay superposición: // El primer participio en la dirección de avance + la longitud del último participio en la dirección inversa = Ingrese la longitud total de la cadena, entonces la dirección hacia adelante e inversa se puede escribir si (izquierda.get (0) .length () + derecho resultMiddle.Add (izquierda.get (0)); resultMiddle.add (right.get (right.size () - 1)); } // Agregar el resultado del participio inequívoco al resultado final para (cadena de cadena: resultado) {resultado.Add (string); } for (cadena String: resultMiddle) {result.add (string); } // El participio almacenado en "serpiente codiciosa correcta" debe ajustarse para reenviar (int i = resultright.size ()-1; i> = 0; i--) {result.add (resultright.get (i)); } resultado de retorno; } / ** * Divida un párrafo en varias oraciones y realice la segmentación de palabras por separado * * @param inputStr * Un párrafo que se dividirá * @return Participle Resultado de este párrafo * / Lista pública <String> Resultados (String InputStr) {// Se utiliza para almacenar la lista de resultados de la segmentación de Word final <Ching> Result = New ArrayList <String> (); // Si se encuentra la puntuación, se dividirá en varias oraciones String Regex = "[,.;!?]"; Cadena [] st = inputstr.split (regex); // Agregue el resultado del participio de cada oración al resultado del participio final para (StriS Stri: ST) {List <String> List = Resultword (STRI); resultado.addall (lista); } resultado de retorno; } public static void main (string [] args) {// Ejemplo: Ven y vea si el precio del hogar es costoso? Entrada de escáner de subastas de tenis de tabla = nuevo escáner (System.in); Cadena str = input.nextline (); WordsPilt WordsPilt = NULL; intente {WordsPilt = new WordsPilt (); } catch (ioException e) {E.PrintStackTrace (); } List <String> list = WordsPilt.Resultword (str); for (String String: List) {System.out.print (String + "/"); }}}El src/dict.txt es un archivo de diccionario, y la configuración es la siguiente:
Bienvenido a Wulin.com Descargar script tutorial de script Descargar material
Los resultados de la operación son los siguientes:
Para obtener más información sobre los algoritmos de Java, los lectores interesados en este sitio pueden ver los temas: "Estructura de datos Java y tutorial de algoritmo", "Resumen de las puntas de nodo de operación de Java DOM", "Resumen de Java Archivo y TIPS de operación de directorio" y "Summary of Java Cache Operation Tips" TIPS ""
Espero que este artículo sea útil para la programación Java de todos.