取引表のヘッダーを探知する
Posted on by Angus Cheng
今回で銀行明細変換をどの様に行うのかの説明をするのは２回目の投稿となります。
previous articleこの投稿内で、文字の抽出と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)
上記のコードは、ページ数、ページのグラフィカルラインの探知方法は取引ヘッダー探知クラスを参考にしてください。グラフィカルラインは通常、表のヘッダーの質を向上させますが、この詳細に関してはまた後で話し合いましょう。
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()
}
その後、単語をライン内へ構造し、各ラインの銀行明細取引表のヘッダーの様な見た目になっているかを確認します。もう一つヘッダーがあればリターンします。それを怠ると、ヘッダーに２つ線が出てきてしまいます。上手くいくと良いですね！上手くいかなければ、ヘッダーが３本になっていないか確認をしてみて下さい。これはあまりきれいな解決策ではありませんが、実際には上手くいくことが多いです。それに、これはパフォーマンスが重要ではない為、必要な時に「ライン探知」法を使えば良いのです。
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)
}
ライン探知は実は遠回しな方法なのです。予想できたと思いますが、元々のアルゴリズムは各ラインずつのヘッダーしか見ていません。ユーザーからエラーの連絡メールが届いたので、複数のラインを同時に確認出来る様、アルゴリズムを向上させました。Kotlinでコード作成した事がない方は少し怖いと思うかもしれませんが、行っている内容としては「ヘッダーの取引解析」法で使用できるラインを使っているだけです。後々、ラインを使い豊かにするという呼び名に変更し、ヘッダー境界の品質を向上させましたが、この方法についてはまた後程お話ししましょう。このコードを理解できなくても問題ありませんし、特に面白くもないので、安心してください。
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を利用する方法をお見せします。下記に単語のリストがあるので、どのヘッダーにどの単語を適合させるのかを見てみましょう。GetXRangeに「日付」と入れると、行ごとにて適合する単語を探していきます。適合させるのは実は知っている単語のサブストリングを探しているのです。なのでgetXRange(“sabalance”) は残高の行に分類されます。
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
)
もしあなたが [冷淡な目つきのミサイルマン]だとしたら(https://en.wikipedia.org/wiki/John_Aaron) これは全ての言語の対応は出来ないという事に気づくと思います。例えば、全ての言語を対応する場合、キーワードのリストを追加する必要があり、書類のプロセスにも時間が掛かります。私が考えたのは Trie data structure の方がキーワードの種類を増やすのには適しているのではないかという事です。最後に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)
}
extendXRangesは取引ヘッダーが探知された後に呼ばれます。垂直ラインを使ってxRangesが延長されます。実際にグラフィカルラインと取引表と見てみると意味が分かると思います。
上記の画像は私の恒生銀行の明細書の一つです。ヘッダーテキストの外接長方形を使用すると、XRangesは赤になります、extendXRanges は書面のグラフィックラインのXRangesを向上させ、XRangesを青に変える事ができます。次のアルゴリズムのステップはXRangesをコラムテキストと関連付ける事ですが、それと共にテキストがXRangesへ公差するかの確認も行います。
上記で確認できる様に、日付 や 取引詳細 数値は全て適切なヘッダーに付いている事が確認できます。XRangesを延長後、全ての数値は適切な形になります。
今回のブログの投稿はこれで終わりです。次回は銀行明細書変換についてのブログを投稿するので、数値とヘッダーがどの様に関連しているのかの詳細を説明します。