Tokenize el texto en función de unas reglas específicas. Algoritmo en C ++

Question

Estoy escribiendo un programa que tokenize el texto de entrada en función de unas reglas específicas. Estoy usando C ++ para esto.

Reglas

Letter 'a' should be converted to token 'V-A'
Letter 'p' should be converted to token 'C-PA'
Letter 'pp' should be converted to token 'C-PPA'
Letter 'u' should be converted to token 'V-U'

Esto es sólo una muestra y en tiempo real que tienen alrededor de 500 normas de este tipo. Si estoy proporcionando de entrada como ' appu ', debe tokenize como ' V-A + C-PPA + V-T '. He implementado un algoritmo para hacer esto y quería asegurarse de que estoy haciendo lo correcto.

Algoritmo

Todas las reglas se mantendrán en un archivo XML con la asignación correspondiente a la ficha. Algo así como

<rules>
  <rule pattern="a" token="V-A" />
  <rule pattern="p" token="C-PA" />
  <rule pattern="pp" token="C-PPA" />
  <rule pattern="u" token="V-U" />
</rules>

1 - Cuando se inicia la aplicación, lea este archivo XML y mantener los valores en un ' std :: mapa '. Este estará disponible hasta el final de la aplicación (aplicación patrón singleton).

2 - Iterar los caracteres de texto de entrada. Para cada carácter, buscar coincidencias. Si lo encuentra, ser más ambicioso y buscar más coincidencias mediante la adopción de los siguientes caracteres de texto de entrada. Haga esto hasta que estamos recibiendo un no partido. Así que por el texto de entrada ' appu ', primer vistazo a un partido de ' a '. Si lo encuentra, tratar de obtener más partido al tomar el siguiente carácter del texto de entrada. Por lo que trata de hacer coincidir ' p ' y se encontró nada. Por lo que sólo devuelve.

3 -. Vuelva a colocar la letra 'a' del texto de entrada ya que conseguimos una ficha para que

4 -. Repetir el paso 2 y 3 con los caracteres restantes en el texto de entrada

Aquí hay una explicación más simple de los pasos

input-text = 'appu'
tokens-generated=''

// First iteration
character-to-match = 'a'
pattern-found = true

// since pattern found, going recursive and check for more matches
character-to-match = 'ap'
pattern-found = false

tokens-generated = 'V-A'

// since no match found for 'ap', taking the first success and replacing it from input text
input-text = 'ppu'

// second iteration
character-to-match = 'p'
pattern-found = true

// since pattern found, going recursive and check for more matches
character-to-match = 'pp'
pattern-found = true

// since pattern found, going recursive and check for more matches
character-to-match = 'ppu'
pattern-found = false

tokens-generated = 'V-A + C-PPA'

// since no match found for 'ppu', taking the first success and replacing it from input text
input-text = 'u'

// third iteration
character-to-match = 'u'
pattern-found = true

tokens-generated = 'V-A + C-PPA + V-U'  // we'r done!

Preguntas

1 - ¿Es este algoritmo se ve muy bien para este problema o hay una mejor manera de abordar este problema

?

2 - Si este es el método correcto, std :: mapa es una buena opción aquí? O tengo que crear mi propio contenedor de clave / valor?

3 - ¿Hay una biblioteca disponible que puede tokenize cadena como el anterior

?

Cualquier ayuda sería apreciada

:)

Answer 1

Así que vas a través de todas las fichas en su mapa en busca de coincidencias? Es lo mismo que usar una lista o matriz, existe; que va a ser una búsqueda ineficiente independientemente.

Una manera mucho más eficaz de encontrar sólo las fichas adecuadas para iniciar o continuar un partido sería para almacenarlos como un trie . Una búsqueda de una carta no le daría un sub-trie que contiene sólo las fichas que tienen esa carta como la primera letra, y luego sólo seguir buscando hacia abajo lo más lejos que puede ir.

---

Editar: permítanme explicar esto un poco más

.

En primer lugar, debo explicar que no estoy familiarizado con ellos, el C ++ std::map, más allá del nombre, lo que hace de este un ejemplo perfecto de por qué se aprende la teoría de este material, así como de los detalles de bibliotecas particulares de programación en particular idiomas siguientes: a menos que la biblioteca está mal usando mal el nombre de "mapa" (que es bastante improbable), el propio nombre me dice mucho sobre las características de la estructura de datos. Sé, por ejemplo, que no va a ser una función que, dada una sola tecla y el mapa, a buscar de manera muy eficiente para y devolver el valor asociado con esa clave, y que también hay probablemente una función que le dará una lista / gama / lo que sea de todas las claves, que puede buscar por sí mismo utilizando su propio código.

Mi interpretación de la estructura de datos es que usted tiene un mapa donde las claves son lo que se llama un patrón, los que están siendo una lista (o matriz, o algo por el estilo) de caracteres, y los valores son los tokens. De este modo, se puede, dado un patrón completo, encontrar rápidamente el token asociado con él.

Por desgracia, mientras que un mapa de este tipo es un buen partido para convertir su formato de entrada XML a una estructura de datos interna, que no es un buen partido a las búsquedas que hay que hacer. Tenga en cuenta que usted no está buscando patrones enteros, pero el primer carácter de un patrón, la producción de un conjunto de posibles símbolos, seguidos por una búsqueda del segundo carácter de un patrón desde dentro del conjunto de patrones presentados por la primera Buscar , y así sucesivamente.

Así que lo que realmente necesita no es un solo mapa, pero los mapas de mapas de mapas, cada uno afinado por un solo carácter. Una búsqueda de "p" en el nivel superior debe darle un nuevo mapa, con dos claves: p, produciendo el token C-PPA, y "todo lo demás", produciendo el token C-PA. Esto es efectivamente una estructura de datos trie.

¿Esto tiene sentido?

Puede ayudar si se empieza por escribir el código de análisis en primer lugar, de esta manera: imaginar otra persona va a escribir las funciones para hacer las operaciones de búsqueda que necesita, y es un programador muy bueno y se puede hacer casi cualquier tipo de magia que se querer. Escribir el código de análisis, concentrarse en hacer que lo más simple y más limpio posible, creando lo interfaz de uso de estas funciones arbitrarias que necesita (aunque no es trivial y conseguir la sustitución de todo el asunto con una función!). Ahora se puede ver en las funciones de búsqueda que terminó con, y que te dice cómo tiene que acceder a su estructura de datos, que le llevará al tipo de estructura de datos que necesita. Una vez que haya averiguado, a continuación, puede encontrar la manera de cargarla.

Answer 2

1. Este método funcionará -. No estoy seguro de que es eficiente, pero debería funcionar

2. Yo usaría el std :: mapa estándar en lugar de su propio sistema.

3. Hay herramientas como lex (o flex) que se puede utilizar para esto. La cuestión sería si se puede regenerar el analizador léxico que construiría cuando cambia la especificación XML. Si la especificación XML no cambia a menudo, usted puede ser capaz de utilizar herramientas como lex para hacer el escaneo y la cartografía más fácilmente. Si la especificación XML puede cambiar según el capricho de los que utilizan el programa, entonces lex es probablemente menos apropiado.

Hay algunas advertencias - sobre todo que tanto lex y flex generan código C, C ++ en lugar de

.

Me gustaría también considerar la búsqueda de la tecnología de coincidencia de patrones - el tipo de cosas que egrep para determinados usos. Esto tiene el mérito de ser algo que se puede manejar en tiempo de ejecución (porque egrep lo hace todo el tiempo). O usted podría ir para un lenguaje de script -. Perl, Python, ... o usted podría considerar algo así como PCRE (Perl Compatible Regular Expressions) biblioteca

Answer 3

Mejor aún, si usted va a utilizar la biblioteca de impulso, siempre hay la biblioteca Boost tokenizer -> http://www.boost.org/doc/libs/1_39_0/libs/tokenizer/index.html

Answer 4

Se puede usar una expresión regular (tal vez el impulso :: biblioteca de expresiones regulares). Si todos los patrones son sólo una cadena de letras, como una expresión regular "(a | p | PP | u)" sería encontrar una coincidencia codicioso. Por lo tanto:

1. Ejecutar un regex_search usando el modelo anterior para localizar el próximo partido
2. Enchufe el partido-texto en el std :: mapa para obtener el texto de reemplazar.
3. Imprimir la entrada de la no emparejado consumido y reemplazar texto a su salida, a continuación, repita 1 en la entrada restante.

Y hecho.

Answer 5

Puede parecer un poco complicado, pero la forma más eficaz de hacerlo es utilizar un gráfico para representar un estado-gráfico. Al principio, pensé boost.statechart ayudaría, pero pensé que no era realmente apropiado. Este método puede ser más eficiente que el uso de un std :: sencilla mapa si hay muchas reglas, el número de posibles caracteres es limitado y la longitud del texto a leer es bastante alto.

Así que de todos modos, el uso de una gráfica sencilla:

0) crear gráfica de "arranque" vértice

1) leer el archivo de configuración XML y crear vértices cuando sea necesario (transición de un "conjunto de caracteres" (por ejemplo, "pp") para una adicional (por ejemplo, "ppa")). Dentro de cada vértice, almacenar una tabla de transición para los próximos vértices. Si "texto clave" es completa, el vértice marca como final y almacenar el texto resultante

2) ahora leer el texto e interpretarlo usando la gráfica. Comience en el vértice de "arranque". (*) Uso tabla para interpretar un personaje y para saltar al nuevo vértice. Si se ha seleccionado ningún nuevo vértice, un error puede ser emitido. De lo contrario, si es nuevo vértice final, imprimir el texto resultante y regresar a inicio vértice. Volver a (*) hasta que no haya más texto a interpretar.

Se puede usar boost.graph para representar el gráfico, pero creo que es demasiado complejo para lo que necesita. Hacer su propia representación personalizado.