読者です 読者をやめる 読者になる 読者になる

pandazx's blog

Hadoop, データ分析など雑多な技術ブログ

お勉強(匿名化、プライバシー、GPS圧縮、誤字脱字対応の照合技術)

匿名化

Scis2014 匿名化(最終版)
匿名化にも銀の弾丸はないという話。
直接的な氏名、会員番号を削除するのは当然として、性別、年齢などの情報は組み合わせると個人特定できてしまう場合がある。
匿名化し過ぎると情報量が落ちて分析に使えなくなる。
一方で政府の出す統計情報が使えない情報かというとそんなこともない。
データと目的によって、匿名化の方法は個別に検討する必要がある。

プライバシー

スマホアプリにおけるアプリケーション・プライバシーポリシー掲載の国際比較調査
https://staff.aist.go.jp/takagi.hiromitsu/paper/scis2014-3D1-1-ichinose-dist.pdf
スマホアプリを通じた情報収集が問題視されることがあるが、アプリのプライバシーポリシーをどの程度、ユーザに提示しているかという調査。
日本の順位は49ヶ国中45位と低い。
個々のスマホアプリ専用のプライバシーポリシーが用意されていると最高点になる。
ある企業が提供するサービス全般のプライバシーポリシーだと低い点になるという評価。
詳細は論文参照。

GPS圧縮

Compression of GPS trajectories
GPSデータを蓄積しようとすると、データ量が無視できない。
そのための圧縮方法。
欲しい情報ではなかったのであまり読んでいない。

誤字脱字対応の照合技術

誤字脱字や伏字を許容する近接辞書照合技術
http://www.anlp.jp/proceedings/annual_meeting/2011/pdf_dir/E5-2.pdf
2つの文字列の類似度を編集距離などで計算して、一定範囲内に収まる文字列を
高速検索する手法には2つのタイプがあり、この論文は1番。

  1. grepによる文字列検索のような単語境界が明確ではないものに対して、網羅的に検出を行う手法
  2. 単語境界が明確なケースで文字列A、文字列Bの近似性を評価する手法

この論文ではトライ木を使って照合の際の検索速度を木の登録数に依存しないようにしている。
誤字、脱字などにも対応するために、通常の単語の登録に加え、「単語、1」という形式で1文字目がスキップされた場合という表記でその単語の文字数分を登録し、検索の際にスキップ処理を行うというようなロジックを提案している。
ただ、誤字脱字が1文字や連続した文字であればいいが、飛び飛びで発生する場合に対応するには計算量が増えて難しいとしている。

この論文の中で計算量を抑えるためにトライ木との完全一致で何文字先まで照合できたかを覚えておき、スキップ照合をその位置まで行うというテクニックを使っている。

トライ木についてwikipediaで勉強。
トライ木 - Wikipedia
登録数が増えても検索速度が変わらないという点がメリット。
プレフィックス共通の多数の短しキーがたくさんある場合はメモリ効率が良い。

関係ないけど、サフィックスアレイについても勉強。
接尾辞配列 - Wikipedia
接尾辞の配列というから、文字列末尾の配列みたいなものかと思っていたら、
接尾辞にする区切り位置を動かして全パターンの接尾辞を持って、それを辞書順にソートした配列のことなのね。

sort

shellでsortする際に文字列比較になってしまって、2よりも10が上に来てしまうなーと思っていたら、-n option をつけるだけで解決したのだった。
わざわざ桁を大きくして、1010, 1002のようにしておくなんてこと、いらんかったんや。