クレームツリーを何とかする（その１）

出願明細書の請求項数が多い場合、請求項の従属関係をクレームツリーで表示させるとチェック作業が捗るかと思いクレームツリーを表示するツールを紹介したいと思います。
クレームツリー表示ツールは既に存在しますが、今回のようにソースコードがあれば必要に応じてカスタマイズが可能になる点で便利かと思います。

program1.py

#実行前にライブラリ導入（pip install anytree）
#part1 前処理（請求項と従属先のセットを作成）

import re
import unicodedata
import copy
meisai = []
ms_base = []
f = open('meisai.txt', 'r')#ANSIで保存すること
ms_base = f.read()
f.close()
ms_base=unicodedata.normalize("NFKC", ms_base)#請求項数の数値を半角にする
meisai = re.split("【",ms_base)#請求項ごとに分割する

clm_gr_base=[]
clmnum=[]
#「請求項」の文字列を検索して正規表現\d+で一桁以上の数値(=請求項)を抽出
for ms_part in meisai:
    clmnum.append(re.findall(r'請求項(\d+)', ms_part))

#二次元リスト（文字列）を二次元リスト（整数）に変換
clm_gr_base = [[int(x) for x in sublist] for sublist in clmnum]

result_list=[]
for elm in clm_gr_base:
    if len(elm)==1:#請求項が１つ＝独立項なので末尾に0を追加
        elm.append(0)
        result_list.append(elm)
        
    elif len(elm)==2:
        result_list.append(elm)
        
    elif len(elm)>2:#最初の要素と2番目以降の要素がセットになったリストに変換する
        first_element = elm[0]
        result_list.extend([[first_element, x] for x in elm[1:]])

clm_gr = sorted(result_list)
print("clm_gr",clm_gr)
print ("-----------")

#part２ クレームツリーの基礎データ（tree2）作成
tree=[copy.deepcopy(clm_gr)]
Tree_z=[]
node_temp=[]
h=0
cmp=0
while cmp==0:
    for node in tree[h]:
        nd_top = node[0]#clm_topに先頭を入れる
        nd_dpd = node[-1]#clm_dpdに従属先を入れる
        if nd_dpd>0:
            for clm in clm_gr:
                clm_top = clm[0]#clm_topに先頭を入れる
                clm_dpd = clm[1]#clm_dpdに従属先を入れる

                if clm_top==nd_dpd:
                    node_temp=copy.deepcopy(node)
                    node_temp.append(clm_dpd)#node_temp末尾に親を足す
                    Tree_z.append(node_temp)#増分を別枠Tree_zに保管する

    if len(Tree_z)>0:                
        tree.append(Tree_z)#増分をtreeと合体させ、次のループの処理対象にする
        h+=1
    else:
        cmp=1#while文の終了条件をセットする
    Tree_z=[]

#フラットな配列にする
tree2 = [item for sublist in tree for item in sublist]

#末尾0を含まない要素（重複）を削除
rmv_lst=[]
for i,node in enumerate(tree2): 
    if node[-1]>0:
        rmv_lst.append(i)
for index in sorted(rmv_lst, reverse=True):
    if 0 <= index < len(tree2):
        tree2.pop(index)

#末尾０を削除
for node in tree2: 
    node.remove(0)

# デフォルト辞書を使って末尾の要素でグループ化
from collections import defaultdict
grouped = defaultdict(list)
for item in tree2:
    key = item[-1]
    grouped[key].append(item)

# グループ化されたリストを新しいリストに変換
tree3 = [grouped[key] for key in sorted(grouped)]
print ("tree3",tree3)
print ("-----------")

#part3 クレームツリー表示
from anytree import Node, RenderTree
with open('clm_tree.txt', 'w') as f:#ツリーの書込み先ファイルをクリアする
     print("", file=f)

for nd_gr in tree3:#tree3の階層を独立項ごとの階層に分けて処理
    child_list=[]
    for nd in nd_gr:
        if len(nd)==1:
            root=Node(nd[0])#要素が１つ＝rootにする
        else:
            if len(nd)==2:
                child_list.append(Node(nd[0],parent=root))#要素が２つ＝parentをrootに設定する
            if len(nd)>2:#要素が２つ以上＝従属するノードを探して、parentに設定する
                nd_tmp= nd[1:]#２つめ以降の要素を取得
                #nd_tmpと同じもの（＝従属するノード）を探す
                position = nd_gr.index(nd_tmp)
                #ノード名（表示数値）としてndの1番目の要素の数値をセット
                child_list.append(Node(nd[0],parent=child_list[position-1]))

# ツリーをファイルに書き込む
    for pre, fill, node in RenderTree(root):
        with open('clm_tree.txt', 'a') as f:#'a'でファイルに追記
            print("%s%s" % (pre, node.name), file=f)
            print("%s%s" % (pre, node.name))
aa=input("press enter")

以下のサンプルをファイル名「meisai.txt」としてANSI形式で保存します。

請求項サンプル

【請求項１】
○○手段を有する情報処理装置。
【請求項２】
前記情報処理装置であって××手段を有する請求項１記載の情報処理装置。
【請求項３】
前記情報処理装置であって△△手段を有する請求項２記載の情報処理装置。
【請求項４】
前記情報処理装置であって◇◇手段を有する請求項２および請求項３記載の情報処理装置。
【請求項５】
○○工程を有する情報処理方法。
【請求項６】
前記情報処理方法であって××工程を有する請求項５記載の情報処理方法。
【請求項７】
○○ステップを有するプログラム。

program1を実行すると以下のように中間データclm_gr、tree3とクレームツリーを表示します。

結果

clm_gr [[1, 0], [2, 1], [3, 2], [4, 2], [4, 3], [5, 0], [6, 5], [7, 0]]
-----------
tree3 [[[1], [2, 1], [3, 2, 1], [4, 2, 1], [4, 3, 2, 1]], [[5], [6, 5]], [[7]]]
-----------
1
└── 2
    ├── 3
    │   └── 4
    └── 4
5
└── 6
7
press enter

「clm_gr」が[]に示す数値は請求項番号です。１つめが請求項番号で、2つめは従属先請求項を示します（従属先が無い場合は0)。例えば請求項１，５，7は独立項で、従属先がないため[1, 0],[5, 0], [7, 0]となります。請求項２は従属先が請求項１のため[2, 1]、請求項３は従属先が請求項２のため[3,2]、請求項４は従属先が請求項２、３のため[4, 2], [4, 3]となります(マルチ従属の場合それぞれ別の[ ]としています）。
clm_grを変換してtree3を生成します。tree3では１つの[ ]に全ての従属先を含むようにし、なおかつ単一の独立項に従属するグループをまとめて１つの[ ]にグループ化しています。例えば請求項１に従属する請求項グループは[[1], [2, 1], [3, 2, 1], [4, 2, 1], [4, 3, 2, 1]]となります。請求項５のグループは[[5], [6, 5]]、請求項７は従属項がないので [[7]]となります。
press enterの表示はEnterキーが入力されるまで表示を継続することを示します。
クレームツリーはファイル名clm_tree.txtで保存します。

プログラムのポイント

(part1)
ここでのポイントは「【請求項４】・・有する請求項２および請求項３・・」となっているのを取り込んで[4, 2, 3]としてリスト化したものを[4, 2], [4, 3]に変換する部分です。プログラムでは以下の行での処理になります。

    elif len(elm)>2:#最初の要素と2番目以降の要素がセットになったリストに変換する
        first_element = elm[0]
        result_list.extend([[first_element, x] for x in elm[1:]])

(part2)
ここでのポイントは「【請求項３】・・・有する請求項２」を[3,2]としてリスト化したものを、さらに請求項2の従属先の請求項1を追加し[3, 2, 1]に変換する部分です。プログラムでは以下の行での処理になります。

    for node in tree[h]:
        nd_top = node[0]#clm_topに先頭を入れる
        nd_dpd = node[-1]#clm_dpdに従属先を入れる
        if nd_dpd>0:
            for clm in clm_gr:
                clm_top = clm[0]#clm_topに先頭を入れる
                clm_dpd = clm[1]#clm_dpdに従属先を入れる

                if clm_top==nd_dpd:
                    node_temp=copy.deepcopy(node)
                    node_temp.append(clm_dpd)#node_temp末尾に親を足す
                    Tree_z.append(node_temp)#増分を別枠Tree_zに保管する

    if len(Tree_z)>0:                
        tree.append(Tree_z)#増分をtreeと合体させ、次のループの処理対象にする
        h+=1
    else:
        cmp=1#while文の終了条件をセットする
    Tree_z=[]

親ループ（for node in tree[h]:）で[3,2]をnd_top(＝３）、nd_dpd(＝2）へ取り込みnd_dpdが子ループ（for clm in clm_gr:）でclm_top(請求項2)と一致した（if clm_top==nd_dpd）場合に、リスト末尾に請求項2の従属先（1）を足し（[3,2,1]）、[3,2,1]を別リストTree_zに追加します。ループが一巡したら別リストTree_zを元リストTreeに追加（Tree_z.append(node_temp)）し、再ループさせます。このようにTree_z追加→ループ処理を繰り返すことで最後の従属先に到達するまでループ処理しています。
一点、clm_dpdにはclmの2番目の要素（clm[1]）を代入、nd_dpd にはnodeの末尾（node[-1]）を代入している点、これは、clmは要素が2つに固定されている一方、nodeは要素が3つ以上になる（[4,3]→[4,3,2]→[4,3,2,1]）ことからnodeの末尾を取るため-1を指定します。そして、nodeの末尾の従属先がclm_topと一致したらその従属先clm_dpdを追加します。このようにして従属先を遡り、[ ]の末尾に追加していくよう処理しています。

(part3)
ここでのポイントはpythonのツリー表示ライブラリanytree を使ってにツリー表示をさせるところになります。
ライブラリanytree を使うためにプログラム実行前に以下のコマンドでライブラリのインストールをしておく必要があります。

pip install anytree

anytreeのライブラリで表示させるために、ツリーの構造を設定する必要があります（以下の処理）。

for nd_gr in tree3:#tree3の階層を独立項ごとの階層に分けて処理
    child_list=[]
    for nd in nd_gr:
        if len(nd)==1:
            root=Node(nd[0])#要素が１つ＝rootにする
        else:
            if len(nd)==2:
                child_list.append(Node(nd[0],parent=root))#要素が２つ＝parentをrootに設定する
            if len(nd)>2:#要素が２つ以上＝従属するノードを探して、parentに設定する
                nd_tmp= nd[1:]#２つめ以降の要素を取得
                #nd_tmpと同じもの（＝従属するノード）を探す
                position = nd_gr.index(nd_tmp)
                #ノード名（表示数値）としてndの1番目の要素の数値をセット
                child_list.append(Node(nd[0],parent=child_list[position-1]))

ポイントとして、例えば [4, 3, 2, 1]のノードの連結先のノード(parent）として[3, 2, 1]を設定する必要があるので、そのためにリストtree3から独立項グループ（nd_gr）階層に分割しさらにノードndに分割し、ループ処理でnd_grの中でノードの2つ目以降の要素nd[1:]全てが一致するノードの位置を探し、その位置（position-1で示される）にあるリストをParentとして設定してchild_listに追加する(同時にノード名としてnd[0]を設定)します（child_list.append(Node(nd[0],parent=child_list[position-1]))）。以上のようにしてツリーの構造の設定が可能になります。

注意点１

今回のプログラムでは従属先が「請求項ｎ」と明記されていることを前提としており、請求項の記載が「請求項ｎまたはｍ」や「請求項ｎないしｍ」といった記載ではうまく動作しません。（手作業で書き換えれば動作しますが）この問題についてはpythonでmeisai.txtを書き換えるプログラムを作成しようと思っています。

注意点２

プログラムが【請求項】の「【」を手掛かりに処理(リストの分割)をしているので、想定しない場所に「【」が存在すると動作がおかしくなる可能性があります。

meisai = re.split("【",ms_base)#請求項ごとに分割する

【】は必ず【請求項】の書式として使用されるようお願いします。

最後に

・pythonのリスト処理機能は今回のようなツリー構造の扱いに非常に適していると思います。またライブラリのおかげでツリー表示自体はプログラム不要で助かりました。
・中間データとして出力しているclm_gr、tree3は別のプログラムにも利用できる（例えばtree3のデータを利用して「前記」表記をチェックするプログラムに適用すれば正確なチェックができる）ようになるかと思っています。
今回の記事がお役に立てれば幸いです。