Parseo

Algoritmo de parseo de ficheros ADIF

En esta sección describiremos el algoritmo básico que esta implementado, luego las optimizaciones que se han llevado a cabo, sobre todo para darle flexibilidad, en lugar de velocidad.

Supongamos un fichero adif que nos cabe en memoria completo en una estructura de tipo string, como el siguiente:

"<call:5>EC5A<band:3>80M<mode:3>SSB<qso_date:8>20200311<time_on:4>1904<eor>"

Paso 1: Corte de apertura

Lo primero que se hace para procesar el fichero es partir el string por el caracter <. En nuestro ejemplo anterior quedaría así:

[
    '',
    'call:5>EC5A',
    'band:3>80M',
    'mode:3>SSB',
    'qso_date:8>20200311',
    'time_on:4>1904',
    'eor>'
]

Esto básicamente nos ha dejado con todas las etiquetas separadas.

Paso 1.1: limpieza

Como es normal la primera posición de la lista suele ser descartada, ya que no hay ninguna etiqueta dentro, está vacia. Otra posibilidad es que el programador haya incluido erroneamente una cabecera a modo de comentarios (incluso le ponen # al principio como si fuese parte del estandar). por lo que tendríamos un bloque de texto inicial.

Estos comentarios pueden tener una gran cantidad de tipologías, pero por ahora la mejor aproximación sería eliminar la posición 0 de la lista si no contiene >.

Con lo que quedaría, en cualquier de los dos casos, así:

[
    'call:5>EC5A',
    'band:3>80M',
    'mode:3>SSB',
    'qso_date:8>20200311',
    'time_on:4>1904',
    'eor>'
]

Paso 2: Corte de valor

A partir de este punto se puede hacer el trabajo en paralelo. En el caso de que haya una carga de trabajo importante se puede recurrir al multihilo para procesar cada posición del array en un hilo independiente; de esta forma podemos aumentar la velocidad, aunque esta optimización no ha sido necesaria.

Similar al paso 1 vamos a partir cada una de las posiciones de la lista por el caracter >, que separa valor y etiqueta.

En nuestro ejemplo quedaría así:

[
    ('call:5','EC5A'),
    ('band:3','80M'),
    ('mode:3','SSB'),
    ('qso_date:8','20200311'),
    ('time_on:4','1904'),
    ('eor','')'
]

Paso 3: Indentificar Campos especiales

Las etiquetas EOR y EOH son las únicas etiquetas que no cumplen el estandar de ADIF en cuanto a la especificación de logitud y tipo; tampoco tienen valor. Esto las hace ser problemáticas, por lo que las convertiremos en objetos, de forma que sean ignorados por el algoritmo de aqui en adelante; puesto que ya estarían correctamente parseados.

En nuestro caso tenemos una etiqueta eor, tras su conversión quedaría así:

[
    ('call:5','EC5A'),
    ('band:3','80M'),
    ('mode:3','SSB'),
    ('qso_date:8','20200311'),
    ('time_on:4','1904'),
    Eor()
]

Paso 4: Procesar Etiquetas

Como se puede ver las etiquetas son ahora fácilmente identificables por partes ya que están divididas por el caracter :. Cortando la etiqueta por este caracter obtendríamos:

[
    (('call','5'),'EC5A'),
    (('band','3'),'80M'),
    (('mode','3'),'SSB'),
    (('qso_date','8'),'20200311'),
    (('time_on','4'),'1904'),
    Eor()
]

Es posible que en la implementación se use una sola tupla para todo el resultado, pero el objetivo de este documento es explicar el algoritmo en su esencia, no ser una guia explicativa del código.

4.1: Validación de tamaño

En este punto también se comprueba que el valor suministrado tiene la longitud reportada por la etiqueta. En caso contrario se reporta un error; como explicamos al final de este documento.

Paso 5: Creando el Campo

En este momento ya podemos crear los objetos parseados de tipo campo. Lo cual es, de nuevo, bastante directo.

[
    Field('call', 'EC5A'),
    Field('band', '80M'),
    Field('mode', 'SSB'),
    Field('qso_date', '20200311'),
    Field('time_on', '1904'),
    Eor()
]

En este caso que se describe, que es el más común, no hemos ejemplificado el tipo de dato. Simplemente es una posición más de la etiqueta y un parámetro opcional del objeto File que se pasaría en la tercera posición.

Paso 6: Serializando los campos

En este punto tenemos una lista muy larga de objetos que representan, en orden, el contenido del fichero ADIF. Nuestra siguiente tarea es agrupar todas las cabeceras en un objeto (si existen) y todos los campos de un record en otro objeto.

La única diferencia entre los dos es si me encuentro un EOH o un EOR, pero en lo esencial es el mismo algoritmo.

El patrón usado aqui es una reducción, o fold left, en otros lenguajes. Puedes encontrar documentación al respecto aqui.

Pero haremos una descripción simplificada para entender el trabajo que se lleva a cabo.

Vamos a recorrer la lista de objetos de uno en uno. Por lo que nos vamos a encontrar una de las siguientes situaciones:

• Me encuentro un campo
• Me encuentro un error
• Me encuentro un EOR o EOH

Si encuentro un campo (Field) entonces tengo que guardarlo en una lista de campos.

Si encuentro un error entonces tengo que guardarlo en una lista de errores.

Si encuentro un EOR o EOH entonces debo crear el campo Record o Cabecera y meter en este la lista de campos y errores. Este nuevo objeto lo guardaré en la lista de resultados, limpiaré las listas usadas (campos y errores) y continuaré procesado campos de la misma forma hasta que llegue al final de la lista de objetos.

Paso 7: conversión a diccionario/json

Este paso es ya bastante sencillo, tantos los objetos de Python como gran cantidad de sus estructuras de datos se pueden traducir directamente a un json, por lo que en este caso dejaremos clara la estructura a la que hemos llegado en este punto:

resutlados = [
    Record(
        campos={
            'call': 'EC5A',
            'band': '80M',
            ...
        },
        tipos={
        },
        errores=[
        ]
    ),
    ...
]

Dentro de un Record campos es un diccionario, y no una lista. Esto se debe a que es mucho más práctico para acceder al dato que una lista, en la que tendríamos que buscar. Nos permite hacer cosas como:

all_calls = map(lambda r: r.campos['call'], resultados)

Lo cual es esencial para crear vectores de puntuación y similares.

Si te fijas el campo que enumera los tipos es tambien un diccionario, por un motivo similar.

Errores si que es una lista, ya que necesito un listado de errores asociado a ese QSO o Cabecera.

Cuando pasamos esta estructura de datos a un json nos encontramos que hay dos tipos de resultados:

• Record
• Header

Como en json no tenemos tipos agregamos un campo “type” que tendrá los valores “qso” o “header” según proceda para su correcta identificación.

Paso 8: Toques finales

Un fichero ADIF no contiene toda la información necesaria para la confección de un diploma o concurso. Para llevar a cabo este necesitamos que cada fila tenga una serie de datos adicionales; unos metadatos que no son del ADIF.

El que cada fila tenga metadatos se hace porque de esa manera el resultado del parseo es procesable fila a fila sin necesidad de tener un contexto extra. Lo que a nivel de algoritmo de proceso nos permite paralelizar las tareas de procesado de los ADIF hasta donde sea necesario/posible.

Los metadatos aprecerán en un campo “_meta”, dentro del json resultante. Y esta información se pasará al programa en su llamada al inicio, para que la pueda agregar a todas las filas.

El fichero final podría quedar como el siguiente:

{
  "type": "qso",
  "fields": {
    "station_callsing": "EA4RCH/p",
    "call": "EC5A",
    "band": "40",
    "mode": "SSB",
    "qso_date": "20161101",
    "time_on": "0400",
    "time_off": "0400"
  },
  "types": null,
  "errors": null,
  "_meta": {
    "type": "activation",
    "activator": "EA4AW",
    "dme": "21060",
    "vertice": "VGH-110"
  }
}

Optimizaciones Acometidas

Lectura por lineas

El algoritmo se complica un poco porque se están cargando los ficheros de datos línea por línea. El principal motivo de esto es la optimización de la memoria; en un primer momento cargar todo en memoria era posible, pero según se han ido añadiendo otras capacidades al cargador, esto ya no era posible.

Orientación al stream

Actualmente se procesa todo linea a linea para evitar que haya multiples copias del mismo contenido en memoria. De igual manera cuando un QSO se ha completado este se escribe en el fichero de salida sin demora.

La parte más crítica de esta aproximación, y la que más problemas puede dar en el futuro es la de detección de linea incompleta. En el caso de algunos programas como el HamRadio Deluxe, un Record se escribe siempre en varias lineas. Aquí pongo un ejemplo:

<a_index:3>0.0 <ant_az:3>0.0 <ant_el:3>0.0 <band:3>40m <call:8>XXXXXX/P <cont:2>EU <country:5>Spain <cqz:2>14 
<distance:7>412.977 <dxcc:3>281 <eqsl_qsl_rcvd:1>R <eqsl_qsl_sent:1>R <force_init:1>N <freq:8>7.179999 
<gridsquare:4>XXXX <ituz:2>37 <k_index:3>0.0 <lotw_qsl_rcvd:1>R <lotw_qsl_sent:1>R <mode:3>SSB <my_city:6>XXXXXX 
<my_cnty:5>Spain <my_country:5>Spain <my_cq_zone:2>14 <my_gridsquare:6>IN80dk <my_itu_zone:2>37 <my_lat:11>XXXX XXXXXX 
<my_lon:11>XXXX XXXXXX <my_name:5>XXXXX <my_rig:7>XXXXXXX <operator:5>XXXXX <pfx:3>XXX <qsl_rcvd:1>R 
<qsl_rcvd_via:1>E <qsl_sent:1>R <qsl_sent_via:1>E <qso_complete:1>Y <qso_random:1>N <rst_rcvd:2>59 <rst_sent:2>59 
<rx_pwr:3>0.0 <sfi:5>157.0 <station_callsign:5>XXXXX <swl:1>N <time_off:6>081418 <time_on:6>081400 <tx_pwr:8>1000.000 
<hrdcountryno:3>281 <submode:3>SSB <qso_date:8>20230528 <EOR>

En este caso, aunque dificil no es extremo, el sistema que va convirtiendo las filas en objetos emitirá campos hasta llegar al EOR. Momento en el que se generará el Record.

El algoritmo está preparado para soportar incluso el recorte de etiquetas entre varias lienas, pero el de valores no funciona muy bien. Aunque este caso no se ha visto en ninguno de los ficheros suministrados es importante saber que es una limitación del algoritmo actual y que es posible que haya que abordarlo en un futuro.

Optimizaciones pendientes

El rendimiento actual del algoritmo es satisfactorio, al menos en el hardware en el que se ha probado hasta ahora. Pero es posible que en un futuro sea necesario usar la escritura asincrona de ficheros, debido a posibles interacciones con otros programas que hagan un uso intensivo del disco.

Versiones descartadas

Hasta llegar a la versión actual se han implementado diferentes aproximaciones, y en todas estas ocasiones el rendimiento ha bajado tanto que se han tenido que descartar en favor una versión más simple.

Máquina de estados

Este tipo de parseos se pueden entender como una máquina de estados lineal, ya que no tienen diferentes comportamientos en función de los datos que todavía no se han parseado. De tal manera que parece un algoritmo eficaz para la tarea.

Desgraciadamente, y debido a la naturaleza de Python, el recorrer el stream de entrada caracter a caracter y modificar así la máquina de estados, tiene un rendimiento pésimo en comparación a usar las funciones de texto (como split).

Se intentó corregir con una librería de máquinas de estado y con varias estrategias en la gestión de texto de entrada como memoización y buffer. Pero seguían sin acerse, ni de lejos, al rendimiento de las operaciones nativas de Python; que están implementadas directamente en C.

Descent Parser

Es un tipo de parser muy usado, sobretodo en el mundo de los lenguajes de programación de proposito específico (DSL). Su increible flexibilidad los hace especialmente útiles cuando la sintaxsis de entrada es rica y tiene unas reglas muy específicas.

De nuevo en este caso, la sencillez del formato hacía este algoritmo mucho más lento que la implementación actual.

Todas las versiones basadas en posiciones

Se ha intentado varias veces el que los errores marcaran en la fila y columna donde estaban los errores.

Todos los agoritmos se han ralentizado en varios órdenes de magnitud en esta tarea.

Podría ser una gran aportación al mundo del software libre; una especie de compilador, parecido al adif doctor, que te marque en el fichero original, con colores y mensajes claros, que es lo que esta mal del mismo.
Pero como estamos ante un escenario donde lo importante es tener el conteo del diploma lo antes posible, tendrá que esperar.