類似文字列検索ライブラリResemblaを公開しました

LINEでClovaの開発をしている上村です。これはLINE Advent Calendar 2017の13日目の記事です。今日は文字列の話をします。

はじめに

与えられた文字列によく似たものを大きな文字列集合から探すということは、古典的でありふれていながら奥が深く難しい問題です。文字列の類似度を正確に見積もるには複雑な計算が必要ですが、膨大な量のコーパスが与えられたときも可能な限り高速に応答を返す必要があります。

検索する文字列の性質をよく把握することも、品質のよい類似文字列検索を行うためには極めて大切です。ここで、今回考える問題の例を見てみます。

問題