检测转账表的表头
Posted on by Angus Cheng
这是系列博客文章中的第二部分，在本系列中，我解释了银行对账单转换器是如何工作的。在上一篇文章我谈到了如何从PDF中提取每个字符及其边界框。在本文中，我将讨论如何使用字符和边界框来检测转账表的头。
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)
在上面的代码中，我们确定了页面的大小，从页面中提取图形线，并调用TransactionHeaderDetector类中的detect方法。通常情况下，使用图形线可以用来提高表头的质量，我们将在后面更详细地讨论这一点。
override fun detect(__unsortedCharacters: List<CharAndBound>, graphicalLines: List<Line>, pageRegion: Rectangle): List<TableHeader> {
val words = merger.merge(__unsortedCharacters)
...
}
首先，我们将字符列合并为单词列。我们通过按字符的Y和X位置对字符进行排序，然后测量字符之间的水平距离和垂直距离来实现这一目的。如果其中某个值超过阈值，我们便认为这是一个新词的开始。下面是一段有趣的代码，CharacterMerger.kt它负责检测单词之间的边界。
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()
}
在此之后，我们将这些单词组成行，并检查每一行，对比下看看他是否对的上银行对账单交易表的标题。如果找到了更多的头，返回headersFound。如果没有找到，就尝试跨行查找头。如果那能够找到，那便太好了！如果不能，我们就一次跨三行查找头。这不是最优雅的解决方案，但在实践中非常有效。在性能方面它不是很友好，在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实际上有点像一个包装函数。您可能已经猜到的，最初这个算法一次只在一行上查找标题。当用户向我发送电子邮件，说他们遇到错误的时候，我改进了算法，使其可以跨多行查看。如果您之前没有用Kotlin写过程序，这可能看起来有点可怕，它真正所做的就是找出应该给parseTransactionHeader方法的那些行。稍后它调用useLinesToEnrich为了提高头的边界质量，我们将在后面讨论该方法。如果您不理解这段代码，不要担心，它并不有趣。
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
}
下面的代码才有趣。我们尝试将每个单词转换成XRange模型，这是一个简单的模型，用于表示表头中的一个头。getXRange神奇地知道一个单词是否是您可能在转账表头中看到的单词。我们分析拉回的xRanges以查看某些列是否存在。如果没有描述、日期、信用、借记或金额列，代码会输出“此单词列表不构成交易标题”。我们还考虑匹配百分比，即整行中有多少字符是“关键字”。匹配百分比需要大于35%才能被视为转账头。这是因为银行对账单上经常出现大量的文字，如果一行或一组行包含“信用”、“日期”和“描述”，那么解析器将错误地说“啊哈！我找到了一个标题“，而实际上它检测到了一些小的关键字。
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)
}
你可能以为我会给你看这个getXRange长什么样，但我只会给你看getXRange使用的数据，这应该会给你一个大致概念，getXRange到底是干什么的。下面我们有一个单词列表，一些匹配器使用这些单词列表来确定一个单词是否可能是某个标题。如果将单词“date”传递给getXRange，它将遍历匹配器列表，尝试将该单词归类为columntype。匹配器实际上是寻找已知单词的子字符串。因此，getXRange（“Sabalance”）将被归类为BALANCE ColumnType。
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
)
如果你是一个有着丰富经验的程序员你会注意到这种方法并不适用于所有语言。假设我要覆盖每一种可能的语言，这意味着我需要添加更多的关键字到列表中，这也意味着我需要对文档中的每一个单词进行更多的处理。我觉得Trie数据结构可能会在关键字列表的大小增加时有用。最后让我们谈谈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)
// 无法在该标题前后找到行，不是一个有效表格
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
}
// 丰富的表头筛减了，不是一个有效表格
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)
}
extendXRanges在检测到事务标头后调用。它尝试使用垂直线来扩展XRanges。这会让具有图形线的真实转账表看起来更清晰。
上图来自我的一张恒生银行对账单。如果我们使用标题文本的边框，我们将得到用红色表示的XRanges。extendXRanges使用文档中的图形线来改进XRanges，这样我们最终得到用蓝色表示的XRanges。该算法的下一步使用XRanges将文本片段与列相关联，它会检查文本片段是否与任何XRanges相交。
如上面所示，Date和Transaction Details值都与正确的标头相交，但是Deposit,Withdrawal或Balance这些值都没有相交。扩展XRanges后，所有值都得以正确解析。
本篇博文到此为止。在下次的银行对账单转换器博客中，我们将更详细地介绍值如何与标题相关联。