Detección de encabezados en la tabla de transacciones

Esta es la segunda parte de una serie de publicaciones en el blog donde explico cómo funciona el convertidor de extractos bancarios. En el artículo anterior hablé sobre cómo extraigo cada carácter y su cuadro delimitador de un PDF. En este artículo, hablaré sobre cómo uso los caracteres y los cuadros delimitadores para detectar los encabezados de la tabla de transacciones.

val pageRegion = Rectangle(0f, 0f, page.cropBox.width, page.cropBox.height)
val lines = LineExtractor(page).extractLines()
val headers = headerDetector.detect(allCharacters, lines, pageRegion).map(::headerTransformer)

En el código anterior, determinamos el tamaño de la página, extraemos las líneas gráficas de la página y llamamos al método de detección en nuestra clase TransactionHeaderDetector. A menudo, las líneas gráficas se pueden usar para mejorar la calidad de los encabezados de una tabla, hablaremos de eso con un poco más a detalle más adelante.

override fun detect(__unsortedCharacters: List<CharAndBound>, graphicalLines: List<Line>, pageRegion: Rectangle): List<TableHeader> {
    val words = merger.merge(__unsortedCharacters)
    ...
}

Primero fusionamos la lista de caracteres en una lista de palabras. Hacemos esto clasificando los caracteres por sus posiciones Y y X y luego midiendo las distancias horizontales y verticales entre los caracteres. Si cualquiera de los valores cruza un cierto umbral, se considera que es el comienzo de una nueva palabra. Aquí está el código interesante de CharacterMerger.kt que es responsable de detectar límites entre palabras.

val xDistance = current.bound.left() - previous.bound.right()
val yDistance = Math.abs(current.bound.bottom() - previous.bound.bottom())
val isCloseEnoughOnX = xDistance <= xThreshold
val isCloseEnoughOnY = yDistance <= yThreshold

if (!isCloseEnoughOnY || !isCloseEnoughOnX) {
    words.add(createTextAndBound(buffer))
    buffer.clear()
}

Después de eso, formamos las palabras en líneas y revisamos cada línea para ver si parece un encabezado para la tabla de transacciones de un extracto bancario. Si encontramos una cabecera más, la devolvemos. Si no lo hacemos, intentamos buscar encabezados en dos líneas a la vez. Si eso funciona, ¡genial! Si no, buscamos encabezados en tres líneas a la vez. Esta no es la solución más elegante, pero en la práctica funciona bastante bien. Además, no es excelente desde el punto de vista del rendimiento, ya que se repite innecesariamente mucho del trabajo realizado en el método detectLines.

override fun detect(__unsortedCharacters: List<CharAndBound>, graphicalLines: List<Line>, pageRegion: Rectangle): List<TableHeader> {
    val textLines = splitByYLevel(words)
    var headersFound = detectLines(textLines, graphicalLines, pageRegion, 1)

    if (headersFound.isNotEmpty()) {
        return headersFound
    }

    headersFound = detectLines(textLines, graphicalLines, pageRegion, 2)

    if (headersFound.isNotEmpty()) {
        return headersFound
    }

    return detectLines(textLines, graphicalLines, pageRegion, 3)
}

detectLines es en realidad un método contenedor. Como habrás adivinado, originalmente este algoritmo solo buscaba encabezados en una línea a la vez. A medida que los usuarios me enviaban correos electrónicos con errores, mejoré el algoritmo para buscar en varias líneas. Si no ha programado en Kotlin, esto puede parecer un poco aterrador, sin embargo todo lo que realmente se está haciendo es averiguar qué líneas pasar al método parseTransactionHeader. Más adelante se llama a useLinesToEnrich para mejorar la calidad de los límites del encabezado, hablaremos de ese método más adelante. Si no entiendes este código, no te preocupes, no es interesante.

private fun detectLines(
    textLines: List<List<TextAndBound>>,
    graphicalLines: List<Line>,
    pageRegion: Rectangle,
    followingLineCount: Int
): List<TableHeader> {
    val headers = textLines.mapIndexedNotNull { index, _ ->
        val toIndex = index + followingLineCount

        if (toIndex > textLines.lastIndex) {
            null
        }
        else {
            val lines = textLines.subList(index, toIndex).flatten()
            parseTransactionHeader(lines)
        }
    }

    val enrichedHeaders = headers.map { useLinesToEnrich(it, graphicalLines, pageRegion, logger) }
    return enrichedHeaders
}

Ahora estamos llegando al código interesante. Intentamos convertir cada palabra en un modelo XRange, que es un modelo simple para representar uno de los encabezados en el encabezado de la tabla. getXRange sabe mágicamente si una palabra es una palabra que podrías ver en el encabezado de una tabla de transacciones. Analizamos los rangos x que retiramos para ver si ciertas columnas están presentes. Si no hay una columna de descripción, fecha, crédito, débito o monto, entonces el código dice “Esta lista de palabras NO constituye un encabezado de transacción”. También consideramos el porcentaje de coincidencia, es decir, cuántos caracteres en toda la línea eran ‘palabras clave’. El porcentaje de coincidencia debe ser superior al 35% para que se considere un encabezado de transacción. Esto se debe a que los extractos bancarios a menudo tienen letra pequeña con toneladas de palabras, y si una línea o un grupo de líneas contiene las palabras “crédito”, “fecha” y “descripción”, el analizador dirá falsamente “¡Ajá! He encontrado un encabezado”, cuando en realidad ha detectado alguna letra pequeña.

data class XRange(val name: String, val start: Float, val end: Float, val columnType: ColumnType?)

private fun parseTransactionHeader(
    lines: List<TextAndBound>
): TableHeader? {
    val result = lines.map(::getXRange)
    val xRanges = result.map { it.first }.sortedBy { it.start }
    val charactersMatched = result.sumOf { it.second }
    val totalCharacters = lines.sumOf { it.text.length }
    val matchPercent = charactersMatched / totalCharacters.toFloat()

    val hasDate = xRanges.any { it.columnType == ColumnType.DATE }
    val hasBalance = xRanges.any { it.columnType == ColumnType.BALANCE }
    val hasCredit = xRanges.any { it.columnType == ColumnType.CREDIT }
    val hasDebit = xRanges.any { it.columnType == ColumnType.DEBIT }
    val hasAmount = xRanges.any { it.columnType == ColumnType.AMOUNT }
    val hasDescription = xRanges.any { it.columnType == ColumnType.DESCRIPTION }
    val hasCreditDebitAmountOrBalance = hasCredit || hasDebit || hasBalance || hasAmount

    if (!hasDate || !hasDescription || !hasCreditDebitAmountOrBalance || matchPercent < 0.35) {
        return null
    }

    logger.info("Match Percent {}/{} = {}%", charactersMatched, totalCharacters, matchPercent * 100)

    val top = lines.minOf { it.bound.top() }
    val bottom = lines.minOf { it.bound.bottom() }
    return TableHeader(xRanges, top, bottom)
}

Podrías pensar que voy a mostrarte cómo se ve getXRange, pero en lugar de eso, solo te mostraré los datos que usa getXRange y eso debería darte una mejor idea de lo que hace getXRange. A continuación, tenemos una lista de palabras y algunos comparadores que usan esas listas de palabras para determinar si una palabra podría ser para un encabezado determinado. Si pasa la palabra “fecha” a getXRange, revisará la lista de coincidencias en un intento de clasificar la palabra como un tipo de columna. En realidad, los comparadores buscan un substring de las palabras conocidas. Por lo tanto, getXRange(“sabalance”) se clasificará como un tipo de columna BALANCE.

private val dateHeaders = listOf("date", "datum", "posted", "posdatum", "achat", "tanggal", "data")
private val balanceHeaders = listOf("balance", "saldo")
private val amountHeaders = listOf("amount", "bedrag", "mutasi")
private val creditHeaders = listOf( "credit", "moneyin", "paid in", "deposit", "krediet", "crédit", "entrate", "deposits")
private val debitHeaders = listOf("debit", "moneyout", "paid out", "withdrawal", "debiet", "débit", "uscite")
private val descriptionHeaders = listOf("description", "particulars", "details", "transaction", "beskrywing", "narrative", "transaksiebeskrywing", "transaksie", "texte", "keterangan", "descrizione")
private val chargeHeaders = listOf("koste", "charge")

private val matchers = listOf(
    { header: TextAndBound -> isDateColumn(header) } to ColumnType.DATE,
    { header: TextAndBound -> isBalanceColumn(header) } to ColumnType.BALANCE,
    { header: TextAndBound -> isCreditColumn(header) } to ColumnType.CREDIT,
    { header: TextAndBound -> isDebitColumn(header) } to ColumnType.DEBIT,
    { header: TextAndBound -> isAmountColumn(header) } to ColumnType.AMOUNT,
    { header: TextAndBound -> isDescriptionColumn(header) } to ColumnType.DESCRIPTION,
    { header: TextAndBound -> isChargeColumn(header) } to ColumnType.CHARGE
)

Si eres un [hombre misil ojos de acero] (https://en.wikipedia.org/wiki/John_Aaron), habrás notado que esto no funcionará para todos los idiomas. Digamos que debía cubrir todos los idiomas posibles, eso significaría agregar a las listas de palabras clave, lo que significaría más procesamiento para cada palabra en el documento. Creo que una [estructura de datos Trie] (https://en.wikipedia.org/wiki/Trie) podría ser útil a medida que las listas de palabras clave aumentan de tamaño. Finalmente, hablemos del método extendXRanges.

val xRanges = header.xRanges.mapIndexed { index, xRange ->
    val mid = xRange.mid()
    val isFirstHeader = index == 0
    val isLastHeader = index == header.xRanges.lastIndex

    val lineBeforeX = getLineBeforeXPosition(linesAtThisLevel, mid, isFirstHeader)
    val lineAfterX = getLineAfterXPosition(linesAtThisLevel, mid, isLastHeader)

    // Wasn't able to find a line before or after this header. Not a valid table
    if (lineBeforeX == null || lineAfterX == null) {
        logger.info("Wasn't able to find a line before or after header named '${xRange.name}'. Not a valid table")
        return null
    }

    // The enriched headers have shrunk. Not a valid table
    if (lineBeforeX > xRange.start || lineAfterX < xRange.end) {
        logger.info("The enriched headers have shrunk. Not a valid table.")
        return null
    }

    xRange.copy(start = lineBeforeX, end = lineAfterX)
}

Se llama a extendXRanges después de que se haya detectado un encabezado de transacción. Se intenta usar líneas verticales para extender los xRanges. Esto tiene más sentido cuando se observa una tabla de transacciones real con líneas gráficas.

La imagen de arriba es de uno de mis estados de cuenta de Hang Seng Bank. Si usamos los rectángulos delimitadores del texto del encabezado, terminaremos con XRanges representados en rojo. extendXRanges usa las líneas de gráficos en el documento para mejorar los XRanges para que terminemos con XRanges representados en azul. El siguiente paso en el algoritmo usa los XRanges para asociar fragmentos de texto con una columna, verifica si un fragmento de texto se cruza con alguno de los XRanges.

Como puede ver arriba, los valores Fecha y Detalles de la transacción se cruzan con el encabezado correcto, sin embargo, ninguno de los valores Depósito, Retiro o Saldo lo hacen. Todos los valores se resuelven correctamente después de extender los XRanges.

Esto es todo por esta publicación del blog. La próxima vez en el blog de Bank Statement Converter hablaremos con más detalle sobre cómo se asocian los valores con los encabezados.