概要

レーベンシュタイン距離というものをご存じだろうか？ざっくりと説明すると、ある文字列と別の文字列を同じ文字列に編集するために最小でどれくらい手数が必要か算出するアルゴリズムで、文字列同士の類似度に応用が可能になる。これは表記ゆれ問題でつきまとう、いわゆる「名寄せ」作業で効果を発揮する。これを活用して、社内のIT資材管理業務のユーザーリスト管理作業の負荷軽減ができた事例について紹介させていただく。レーベンシュタイン距離については、詳しく解説されている下記サイトを参照して欲しい。【技術解説】似ている文字列がわかる！レーベンシュタイン距離とジャロ・ウィンクラー距離の計算方法とは

管理は続くよ、どこまでも

IT土方まず、IT資材管理業務を簡単に説明すると、セキュリティ担保の文脈で、情シスにて管理するIT資材（PCなど）を、社内外の誰に貸与しているのか、使用権を割り当てているのか、また使用されていない端末は無いか、といった点を定期的にチェックする必要がある。ただ、管理する上で必要な情報が集積されているIT資材管理用ユーザーリストが表記ゆれもあり使いづらく、チェックに結構な工数がかかる見込み。また、これは今回だけでなく定期的、継続的に行う必要がある。こういう仕事は自分一人で抱えたくない。どうしたものか・・・。

【チェック対象】手入力で更新されるIT資材管理用ユーザーリスト

情シスにて管理するIT資材の一覧表。重要なポイントとして、このリストは、様々な発生源から人間が手入力で追加、更新することによってレコードが蓄積されていく、と思っていただきたい。その業務フローの妥当性や是非はともかくとして、手入力によって生成されるリストである以上、その時点で誤字、脱字などのミスは発生し得るものとなる。また、運用上の何らかのミスや逸脱、あるいは手違いなども発生する。このような要因によって、ある時点における、あるIT資材の実際の使用者がユーザーリストに記載されたユーザーと異なっている、という状況は日々発生する。これらを追跡調査し、ユーザーリストを正しい状態に保つ必要がある。

監視システムのログ

監視する人修正作業を行うにあたっての情報源として、ユーザーリストの他に、情シスで使っている監視システムより出力される監視システムのログを用いる。監視システムのログでは、例えばWindowsのPCであれば、PCのコンピューター名、ログインユーザーのアカウント、ユーザー名といった情報が機械的に収集されている。このログに残された使用者の痕跡こそが、現時点でのその資材の「本当の使用者」の痕跡であると言える。

一義的には、ログに残された使用者の痕跡とユーザーリストに記された使用者を照合して一致しない場合、リストか、あるいは資材の使用実態をあるべき状態に修正していく、というのが実際の修正作業である。

照合作業の面倒さ

名前不一致の例例えば、山田太郎さんという人がいたとして、その名前の表記というのは山田太郎でもTaro Yamadaでもあり得る。何らかの業務の性質によって使い分けられているようだ。日本国外出身のユーザーはさらに複雑で、著名人で言えば、Ruy Gonçalves Ramos Sobrinhoというブラジル出身のアスリートは、ラモス瑠偉やラモスるいという書き方でも通用するのはご存知の通りだ。

ユーザーリストの修正においては、いわゆる「名寄せ」による表記の統一は重要ではない。表記の統一はそれはそれで意味があるが、ここでより重要なのは、繰り返しになるが管理上の使用者と実際の使用者が異なっているケースを見つけてそれを正すことだ。管理上の使用者と実際の使用者が同じようだが、文字列上では一致しないものとしては、以下のようなケースが頻出した。

漢字間違いや表記ゆれによる不一致。例）高橋と髙橋
１人複数端末を使用によるユーザー名の不一致。例）山田（●●作業用）
日本語とアルファベットによる不一致　例）山田とYamada

この照合作業と修正作業は１回やったらOKではなく、セキュリティの担保など管理上の目的から、__定期的反復的に行われるべき作業なので、そこに要する労力は極小化することが望ましい。__かといって、修正作業をしなくてもいいように、システム上のユーザー情報を規律正しいものにするような予防的統制には、実務上の生産性や作業性を考慮すると難しい。なので、従来通りのユーザーリスト管理を前提とした照合作業の方針は変えずに、その負荷を軽減する工夫をしたい。

工夫するポイント

管理上の使用者と実際の使用者が異なっている場合の追跡調査を行うリストを作成する。リストの大まかな方針としては、__個人名の表記の幅をある程度許容できるように、ユーザーリストとのログ上のユーザー情報の文字列の類似度を算出__する。これにより、類似度が低いものは対応の優先度が高くなるユーザーリスト管理用の追跡調査リストを作成することにした。

レーベンシュタイン距離の実装

前置きが大変長くなったが、ここでようやくレーベンシュタイン距離が登場する。当初は類似度を算出する手段として、機械学習周りで何か利用できるアルゴリズムがあるのか探していたが、冒頭のレーベンシュタイン距離の解説を目にして、正に求めていたものだったので採用することにした。今回は、__類似度＝1 - (レーベンシュタイン距離÷文字数）__として算出する。この業務以外に広い範囲で使用することも視野に入れて、Google Apps Script（GAS）でスクラッチで実装してみた。

function levenshteinSimilarity(str1, str2) {
  var m = Math.max(str1.length, str2.length);
  var d = levenshteinDistance(str1, str2);
  return 1 - (d / m);
}

//参考ブログ：レーベンシュタイン距離で文字列の類似度を高速に取得する
//https://www.bugbugnow.net/2020/02/levenshtein-distance.html
function levenshteinDistance(str1, str2) {
  var r, c, cost, 
      d = [];

  for (r=0; r<=str1.length; r++) {
    d[r] = [r];
  }
  for (c=0; c<=str2.length; c++) {
    d[0][c] = c;
  }
  for (r=1; r<=str1.length; r++) {
    for (c=1; c<=str2.length; c++) {
      //cost = str1[r-1] == str2[c-1] ? 0: 1;
      cost = str1.charCodeAt(r-1) == str2.charCodeAt(c-1) ? 0: 1;
      d[r][c] = Math.min(d[r-1][c]+1, d[r][c-1]+1, d[r-1][c-1]+cost);
    }
  }
  return d[str1.length][str2.length];
}

※levenshteinDistance関数は「レーベンシュタイン距離で文字列の類似度を高速に取得する」をそのまま使わせていただいてます。

【参考】pythonではより楽に実装が可能

!pip install python-Levenshtein
import Levenshtein

def get_leven_sim(str1,str2):
    #レーベンシュタイン距離の取得
    lev_dist = Levenshtein.distance(str1, str2)
    n = len(str1) if len(str1) > len(str2) else len(str2)
    lev_dist_normalized = lev_dist / n
    #0→完全不一致、1→完全一致
    lev_sim = 1 - lev_dist_normalized
    return lev_sim

翻訳APIによる山田→Yamada

類似度が算出できるようになったが、日本語とアルファベットによる不一致のパターンが存在することで、類似度が０になる問題が出てきた。これには翻訳APIを活用することにした。Google翻訳などは日常的にお世話になっている人は多いと思うが、実は名前のアルファベット化にも使用することが出来る。例えば「黒須太郎」→「Kurosu Taro」と変換される。ただし、一般的な名前のみに機能するのでちょっと変わった名前や苗字は100%正しいものになるわけではない。 Class LanguageApp 　Google公式リファレンス

結果

以下のような追跡調査リストが作成できた。

まずスコアが最大値の「1」の群であるが、これは完全一致の群である。類似度1

続いて、0.8～0.4くらいのスコアの群をご覧いただきたい。類似度0.8-0.4 このあたりには、機械的な照合では違うものとされつつ、__目視の確認であれば「たぶんユーザーリストの通りの使用者が使っているな」と思える__ものが揃っている。

そして、0.4未満の群は以下のようになる。類似度0.4- かなり混沌としてきており、追跡調査が必要そうなものが多くなってくる。

文字列の類似度の効果

おしゃれなおじさんご覧のように、文字列の比較結果の数値そのものは、それだけではさほど意味のあるものにはならない。しかしながら、修正作業という極めて実務的なシーンを想像していただくと、このように類似度によってソートされることの意味をご理解いただけるのではないだろうか。単純に頭から順番に不一致レコードを処理していくのは、修正や調査が必要なものとそうでないものが入り混じっており、見ているだけでも疲れるような作業だ。追跡調査リストが類似度によってソートされていれば、例えばスコア0.5以上のものは正しいものと見做しておおまかに俯瞰するに留め、まずは0.5以下のレコードについて分割並行作業を割り当てていくなど、効率的にユーザーリスト管理のタスクを計画していくことが可能となる。また、例えば1か月に1度の照合の結果、99.9％以上のレコードが類似度0.7以上をキープできるよう業務改善やレギュレーションの見直しを行う、その取り組みの評価に用いる、など、活用の幅は広い。

そして何より、単純で面倒な確認作業にこういった一手間を加えて見せると、なんだかとても情シスっぽくてオシャレなのである、とは言えないだろうか。

以上

文字列の類似度を算出したらリストの名寄せや管理の負担が軽くなった話

概要