Deno , TypeScript , Functional Programming , Text Processing

Saturday, June 10, 2023

食品の原材料表記の括弧の多重入れ子文字列をパースしてトークンに分割する

たとえば無印良品のこの食品フライパンでつくるミールキット　海老といかのアヒージョの商品表示情報のPDFをみると以下のような文字列が原材料名に記載されています。

ブロッコリー(エクアドル)、揚げじゃがいも(じゃがいも(国産)、植物油脂)、殻付き海老(インド)、いか(中国)、(一部にえび・いかを含む)

このように括弧が入れ子で多重に出現している文字列、しかも、一重/二重/三重・・・ n 重のバリエーションがある文字列をパースすることを考えたい。

最終的には以下のように括弧で括られた部分を AST(Abstract syntax tree) に変換して、各トークンをその括弧の包含関係を生かした状態で把握できるようにしたい。

ingredients-AST

この文字列をパースするための言語は TypeScript を使います。 TypeScript の実行には Deno を使います。

カンマで区切る

最初のステップとして、カンマ「、」でこの文字列を分割することを考えます。まずは安易に split(/、/) してみます。

parser1.ts

const text = 'ブロッコリー(エクアドル)、揚げじゃがいも(じゃがいも(国産)、植物油脂)、殻付き海老(インド)、いか(中国)、(一部にえび・いかを含む)'

const r = text.split(/、/)
console.log(r)

実行します。

$ deno run parser1.ts
[
  "ブロッコリー(エクアドル)",
  "揚げじゃがいも(じゃがいも(国産)",
  "植物油脂)",
  "殻付き海老(インド)",
  "いか(中国)",
  "(一部にえび・いかを含む)"
]

ほとんど意図した部分で分割できていますが、 揚げじゃがいも の部分が意図通り分割できていません。
つまり、そこは括弧の途中で分割してほしくはなく、以下のかたまりのままになってほしい。

揚げじゃがいも(じゃがいも(国産)、植物油脂)

これを意図通り分割できるようにパーサーを書くことにします。

parse1

まずは小手調として、再帰関数 parse1 を定義して、一文字づつに分割するようにコードします。

const head = (t:string): string => { return t.substring(0,1) }
const tail = (t:string): string => { return t.substring(1) }

const parse1 = (t: string, acc: string[]): string[] => {
    if( t.length==0 ){
        return acc
    } else {
        const a = head(t)
        const next = tail(t)
        return parse1(next, acc.concat([a]))
    }
}

const text = 'ブロッコリー(エクアドル)、揚げじゃがいも(じゃがいも(国産)、植物油脂)、殻付き海老(インド)、いか(中国)、(一部にえび・いかを含む)'

const r = parse1(text, [])
console.log(r)

実行します。

$ deno run parser1.ts
[
  "ブ", "ロ", "ッ", "コ", "リ", "ー", "(", "エ", "ク",
  "ア", "ド", "ル", ")", "、", "揚", "げ", "じ", "ゃ",
  "が", "い", "も", "(", "じ", "ゃ", "が", "い", "も",
  "(", "国", "産", ")", "、", "植", "物", "油", "脂",
  ")", "、", "殻", "付", "き", "海", "老", "(", "イ",
  "ン", "ド", ")", "、", "い", "か", "(", "中", "国",
  ")", "、", "(", "一", "部", "に", "え", "び", "・",
  "い", "か", "を", "含", "む", ")"
]

うまくいきました。

今度は、意図したカンマ「、」の区切りでテキストを分割するように修正します。考え方としては、オープン括弧とクローズ括弧を数えて通常状態と括弧内状態とを識別できるようにします。（状態遷移を使う）

ここでは、括弧を数える parenCount という変数を導入して、

オープン括弧が出現したら +1
クローズ括弧が出現したら -1

することにします。

したがって、 (parencount==0) が括弧の外側、 (parenCount > 0) が括弧の内側の状態を表します。あとは、括弧の外側状態であれば、カンマを区切り文字として扱い、そうでなければ（括弧の内側状態）カンマを区切り文字として扱わない、という処理をすればOKです。

さらに蓄積変数 acc を作り出す部分を工夫して、区切り文字でなければ、accの最後の要素の文字列に足す、という処理を入れています。

これをコードします。

const head = (t:string): string => { return t.substring(0,1) }
const tail = (t:string): string => { return t.substring(1) }

const parse1 = (t: string, parenCount: number, acc: string[]): string[] => {
    if( t.length==0 ){
        return acc
    } else {
        const a = head(t)
        const next = tail(t)

        if( a=='(' ) {
            return parse1(
                next,
                parenCount+1,
                acc.slice(0,-1).concat([`${acc[acc.length-1]}${a}`]))
            
        } else if( a==')' ) {
            return parse1(
                next,
                parenCount-1,
                acc.slice(0,-1).concat([`${acc[acc.length-1]}${a}`]))
        } else if( a=='、' && parenCount==0 ) {
            return parse1(next, parenCount, acc.concat(['']))
        } else {
            return parse1(
                next,
                parenCount,
                acc.slice(0,-1).concat([`${acc[acc.length-1]}${a}`]))
        }
    }
}

const text = 'ブロッコリー(エクアドル)、揚げじゃがいも(じゃがいも(国産)、植物油脂)、殻付き海老(インド)、いか(中国)、(一部にえび・いかを含む)'

const r = parse1(text, 0, [''])
console.log(r)

パースする文字をみて (, ), 、 がきたら特別対処する、というコードです。実行してみます。

$ deno run parser1.ts
[
  "ブロッコリー(エクアドル)",
  "揚げじゃがいも(じゃがいも(国産)、植物油脂)",
  "殻付き海老(インド)",
  "いか(中国)",
  "(一部にえび・いかを含む)"
]

意図通りに分割できるようになりました。

parse2

それでは次に分割できた文字列それぞれをさらにパースします。

つまり、たとえば、「ブロッコリー(エクアドル)」であれば、以下のように分割したい。

- ブロッコリー[mainToken]
  - エクアドル[subToken]

そして、「揚げじゃがいも(じゃがいも(国産)、植物油脂)」であれば、以下のように分割したい。

- 揚げじゃがいも[mainToken]
  - じゃがいも[subToken]
    - 国産[subsubToken]
  - 植物油脂[subToken]

要するに以下のようにASTに変換した上で各トークンを把握したい。

ingredients-AST

それでは、このようなAST変換するパーサー parse2 を書いていきます。
話を簡単にするため、いったん parse1 のことは忘れて、「揚げじゃがいも(じゃがいも(国産)、植物油脂)」という文字列だけをパースするコード parse2 を考えます。

まずパースした文字列を蓄積するための TreeNode を定義します。

type TreeNode = {
    text: string,
    parentNode: TreeNode|null,
    children: TreeNode[]
}

テキストからこの TreeNode を構築する parse2 関数のシグニチャーはこれです。

const parse2 = (t: string, treeNode: TreeNode): TreeNode => {
    ...
}

対象文字列を先頭からパースしていき、特別な文字 (, ), 、 が出現したら、適切に TreeNode に対する処理を行い再帰する、という流れです。

parser2.ts

type TreeNode = {
    text: string,
    parentNode: TreeNode|null,
    children: TreeNode[]
}

const toTreeNode = (text: string, parentNode: TreeNode|null, children: TreeNode[]): TreeNode => {
    return {
        text: text,
        parentNode: parentNode,
        children: children
    }
}


const head = (t:string): string => { return t.substring(0,1) }
const tail = (t:string): string => { return t.substring(1) }

const parse2 = (t: string, treeNode: TreeNode): TreeNode => {
    if( t.length==0 ){
        return treeNode
    } else {
        const a = head(t)
        const next = tail(t)

        if( a=='(' ) {
            const newTreeNode = toTreeNode('', treeNode, [])
            treeNode.children = treeNode.children.concat([newTreeNode])
            return parse2(next, newTreeNode)
        } else if( a==')' ) {
            if( treeNode.parentNode==null ){
                return treeNode // error!
            } else {
                return parse2(next, treeNode.parentNode)
            }
        } else if( a=='、' ) {
            if( treeNode.parentNode==null ){
                return treeNode // error!
            } else {
                const newTreeNode = toTreeNode('', treeNode.parentNode, [])
                treeNode.parentNode.children = treeNode.parentNode.children.concat([newTreeNode])
                return parse2(next, newTreeNode)
            }
        } else {
            treeNode.text = `${treeNode.text}${a}`
            return parse2(next, treeNode)
        }
    }
}

const text = '揚げじゃがいも(じゃがいも(国産)、植物油脂)'
const rootTreeNode = toTreeNode('', null, [])
const r = parse2(text, rootTreeNode)
console.log(r)

実行します。

$ deno run parser2.ts
<ref *1> {
  text: "揚げじゃがいも",
  parentNode: null,
  children: [
    { text: "じゃがいも", parentNode: [Circular *1], children: [ [Object] ] },
    { text: "植物油脂", parentNode: [Circular *1], children: [] }
  ]
}

うまくいっているようですが、三階層目がどうなっているかわかりません。自前で結果の TreeNode を表示するコードを書きます。

const dumpTreeNode = (treeNode: TreeNode, level: number): string[] => {
    const indent = [...Array(level).keys()].map( (_)=> '  ' ).join('')

    const nsub = [...Array(level).keys()].map( (_)=> 'sub' ).join('')
    let tokenKind = 'mainToken'
    if( nsub!='' ){ tokenKind = `${nsub}Token` }

    const item = `${indent}- ${treeNode.text}[${tokenKind}]`

    if( treeNode.children.length==0 ){
        return [item]
    } else {
        const items = treeNode.children.map((childTreeNode)=>{
            return dumpTreeNode(childTreeNode, (level+1))
        }).flat()

        return [item].concat(items)
    }
}

実行します。

$ deno run parser2.ts
- 揚げじゃがいも[mainToken]
  - じゃがいも[subToken]
    - 国産[subsubToken]
  - 植物油脂[subToken]

できました。

parser2.ts のコード全体を掲載します。

type TreeNode = {
    text: string,
    parentNode: TreeNode|null,
    children: TreeNode[]
}

const toTreeNode = (text: string, parentNode: TreeNode|null, children: TreeNode[]): TreeNode => {
    return {
        text: text,
        parentNode: parentNode,
        children: children
    }
}


const head = (t:string): string => { return t.substring(0,1) }
const tail = (t:string): string => { return t.substring(1) }

const parse2 = (t: string, treeNode: TreeNode): TreeNode => {
    if( t.length==0 ){
        return treeNode
    } else {
        const a = head(t)
        const next = tail(t)

        if( a=='(' ) {
            const newTreeNode = toTreeNode('', treeNode, [])
            treeNode.children = treeNode.children.concat([newTreeNode])
            return parse2(next, newTreeNode)
        } else if( a==')' ) {
            if( treeNode.parentNode==null ){
                return treeNode // error!
            } else {
                return parse2(next, treeNode.parentNode)
            }
        } else if( a=='、' ) {
            if( treeNode.parentNode==null ){
                return treeNode // error!
            } else {
                const newTreeNode = toTreeNode('', treeNode.parentNode, [])
                treeNode.parentNode.children = treeNode.parentNode.children.concat([newTreeNode])
                return parse2(next, newTreeNode)
            }
        } else {
            treeNode.text = `${treeNode.text}${a}`
            return parse2(next, treeNode)
        }
    }
}

const dumpTreeNode = (treeNode: TreeNode, level: number): string[] => {
    const indent = [...Array(level).keys()].map( (_)=> '  ' ).join('')

    const nsub = [...Array(level).keys()].map( (_)=> 'sub' ).join('')
    let tokenKind = 'mainToken'
    if( nsub!='' ){ tokenKind = `${nsub}Token` }

    const item = `${indent}- ${treeNode.text}[${tokenKind}]`

    if( treeNode.children.length==0 ){
        return [item]
    } else {
        const items = treeNode.children.map((childTreeNode)=>{
            return dumpTreeNode(childTreeNode, (level+1))
        }).flat()

        return [item].concat(items)
    }
}

const text = '揚げじゃがいも(じゃがいも(国産)、植物油脂)'
const rootTreeNode = toTreeNode('', null, [])
const r = parse2(text, rootTreeNode)
const r1 = dumpTreeNode(r, 0)
console.log(r1.join('\n'))

parse1 と parse2 を使って全体の文字列をパースしてトークンを得る

parser1.ts をモジュールとして使うために以下の記述を parser1.ts の最後に追加します。

const splitText = (text: string): string[] => {
    return parse1(text, 0, [''])
}

export { splitText }

parser2.ts をモジュールとして使うために以下の記述を parser2.ts の最後に追加します。

const buildTreeNode = (text: string): TreeNode => {
    const rootTreeNode = toTreeNode('', null, [])
    return parse2(text, rootTreeNode)
}

export { buildTreeNode, dumpTreeNode }

parser1.ts と parser2.ts で export した関数を使って文字列をパースする main.ts を用意します。

import { splitText } from './parser1.ts'
import { buildTreeNode, dumpTreeNode } from './parser2.ts'

const text = 'ブロッコリー(エクアドル)、揚げじゃがいも(じゃがいも(国産)、植物油脂)、殻付き海老(インド)、いか(中国)、(一部にえび・いかを含む)'

const textBlocks = splitText(text)
const resultList = textBlocks.map( (textBlock)=> {
    const treeNode = buildTreeNode(textBlock)
    return dumpTreeNode(treeNode, 0)
}).flat()

console.log(resultList.join('\n'))

実行します。

$ deno run main.ts
- ブロッコリー[mainToken]
  - エクアドル[subToken]
- 揚げじゃがいも[mainToken]
  - じゃがいも[subToken]
    - 国産[subsubToken]
  - 植物油脂[subToken]
- 殻付き海老[mainToken]
  - インド[subToken]
- いか[mainToken]
  - 中国[subToken]
- [mainToken]
  - 一部にえび・いかを含む[subToken]

うまくいきました。

対象となる文字列を変えても意図通り作動するか試してみましょう。

こちらの商品抹茶の小豆クリームサンドクッキーの原材料名文字列で試してみます。

const text = '小麦粉(国内製造)、ショートニング、麦芽糖、砂糖、乾燥小豆甘納豆(小豆、砂糖)、あん(生あん、砂糖、水あめ)、マーガリン、でん粉、抹茶加工品、チョコレート、粉末小豆、液全卵、全粉乳、食塩、あずきソース、洋酒/グリセリン、香料、乳化剤、酒精、膨脹剤、着色料(クチナシ、カラメル、紅花黄、ラック、カロチノイド)、酸化防止剤(ビタミンE)、増粘剤(キサンタンガム)、(一部に小麦・卵・乳成分・大豆を含む)'

実行。

$ deno run main.ts
- 小麦粉[mainToken]
  - 国内製造[subToken]
- ショートニング[mainToken]
- 麦芽糖[mainToken]
- 砂糖[mainToken]
- 乾燥小豆甘納豆[mainToken]
  - 小豆[subToken]
  - 砂糖[subToken]
- あん[mainToken]
  - 生あん[subToken]
  - 砂糖[subToken]
  - 水あめ[subToken]
- マーガリン[mainToken]
- でん粉[mainToken]
- 抹茶加工品[mainToken]
- チョコレート[mainToken]
- 粉末小豆[mainToken]
- 液全卵[mainToken]
- 全粉乳[mainToken]
- 食塩[mainToken]
- あずきソース[mainToken]
- 洋酒/グリセリン[mainToken]
- 香料[mainToken]
- 乳化剤[mainToken]
- 酒精[mainToken]
- 膨脹剤[mainToken]
- 着色料[mainToken]
  - クチナシ[subToken]
  - カラメル[subToken]
  - 紅花黄[subToken]
  - ラック[subToken]
  - カロチノイド[subToken]
- 酸化防止剤[mainToken]
  - ビタミンE[subToken]
- 増粘剤[mainToken]
  - キサンタンガム[subToken]
- [mainToken]
  - 一部に小麦・卵・乳成分・大豆を含む[subToken]

意図通り作動しています。

まとめ

最後にまとめとして最終的にできたコードを掲載します。

parser1.ts

const head = (t:string): string => { return t.substring(0,1) }
const tail = (t:string): string => { return t.substring(1) }

const parse1 = (t: string, parenCount: number, acc: string[]): string[] => {
    if( t.length==0 ){
        return acc
    } else {
        const a = head(t)
        const next = tail(t)

        if( a=='(' ) {
            return parse1(
                next,
                parenCount+1,
                acc.slice(0,-1).concat([`${acc[acc.length-1]}${a}`]))
            
        } else if( a==')' ) {
            return parse1(
                next,
                parenCount-1,
                acc.slice(0,-1).concat([`${acc[acc.length-1]}${a}`]))
        } else if( a=='、' && parenCount==0 ) {
            return parse1(next, parenCount, acc.concat(['']))
        } else {
            return parse1(
                next,
                parenCount,
                acc.slice(0,-1).concat([`${acc[acc.length-1]}${a}`]))
        }
    }
}

const splitText = (text: string): string[] => {
    return parse1(text, 0, [''])
}

export { splitText }

parser2.ts

type TreeNode = {
    text: string,
    parentNode: TreeNode|null,
    children: TreeNode[]
}

const toTreeNode = (text: string, parentNode: TreeNode|null, children: TreeNode[]): TreeNode => {
    return {
        text: text,
        parentNode: parentNode,
        children: children
    }
}


const head = (t:string): string => { return t.substring(0,1) }
const tail = (t:string): string => { return t.substring(1) }

const parse2 = (t: string, treeNode: TreeNode): TreeNode => {
    if( t.length==0 ){
        return treeNode
    } else {
        const a = head(t)
        const next = tail(t)

        if( a=='(' ) {
            const newTreeNode = toTreeNode('', treeNode, [])
            treeNode.children = treeNode.children.concat([newTreeNode])
            return parse2(next, newTreeNode)
        } else if( a==')' ) {
            if( treeNode.parentNode==null ){
                return treeNode // error!
            } else {
                return parse2(next, treeNode.parentNode)
            }
        } else if( a=='、' ) {
            if( treeNode.parentNode==null ){
                return treeNode // error!
            } else {
                const newTreeNode = toTreeNode('', treeNode.parentNode, [])
                treeNode.parentNode.children = treeNode.parentNode.children.concat([newTreeNode])
                return parse2(next, newTreeNode)
            }
        } else {
            treeNode.text = `${treeNode.text}${a}`
            return parse2(next, treeNode)
        }
    }
}


const dumpTreeNode = (treeNode: TreeNode, level: number): string[] => {
    const indent = [...Array(level).keys()].map( (_)=> '  ' ).join('')

    const nsub = [...Array(level).keys()].map( (_)=> 'sub' ).join('')
    let tokenKind = 'mainToken'
    if( nsub!='' ){ tokenKind = `${nsub}Token` }

    const item = `${indent}- ${treeNode.text}[${tokenKind}]`

    if( treeNode.children.length==0 ){
        return [item]
    } else {
        const items = treeNode.children.map((childTreeNode)=>{
            return dumpTreeNode(childTreeNode, (level+1))
        }).flat()

        return [item].concat(items)
    }
}


const buildTreeNode = (text: string): TreeNode => {
    const rootTreeNode = toTreeNode('', null, [])
    return parse2(text, rootTreeNode)
}

export { buildTreeNode, dumpTreeNode }

main.ts

import { splitText } from './parser1.ts'
import { buildTreeNode, dumpTreeNode } from './parser2.ts'

//const text = 'ブロッコリー(エクアドル)、揚げじゃがいも(じゃがいも(国産)、植物油脂)、殻付き海老(インド)、いか(中国)、(一部にえび・いかを含む)'
const text = '小麦粉(国内製造)、ショートニング、麦芽糖、砂糖、乾燥小豆甘納豆(小豆、砂糖)、あん(生あん、砂糖、水あめ)、マーガリン、でん粉、抹茶加工品、チョコレート、粉末小豆、液全卵、全粉乳、食塩、あずきソース、洋酒/グリセリン、香料、乳化剤、酒精、膨脹剤、着色料(クチナシ、カラメル、紅花黄、ラック、カロチノイド)、酸化防止剤(ビタミンE)、増粘剤(キサンタンガム)、(一部に小麦・卵・乳成分・大豆を含む)'

const textBlocks = splitText(text)
const resultList = textBlocks.map( (textBlock)=> {
    const treeNode = buildTreeNode(textBlock)
    return dumpTreeNode(treeNode, 0)
}).flat()

console.log(resultList.join('\n'))

以上です。