不適切語を構造的に回避するアルファベット識別子の符号化提案: Markovian-Base19/27 (MB1927) 方式

TL;DR

Base36やBase64などを識別子として使う際、不適切語の出現リスクがある。

本提案では、従来の禁止語フィルタではなく、マルコフ連鎖的な連接フィルタを用いて構造的に回避する方式を採用。

多言語の不適切語を一定割合で回避しながら、英数字による一意性と順序性を保証する符号化方式「MB1927」を設計・実装。

なお本提案はCC0ライセンスとする。

はじめに

ファイル名、ユーザーID、URLなどで、英数字を使った一意の識別子を生成する際に、Base36やBase64、Base32などが、16進を超える情報圧縮の符号化方式として比較的よく用いられると思います。

これらを用いてランダムな文字列を生成する際や数値をエンコードする際に、不適切語(いわゆる卑罵語・vulgar word)となる組み合わせが偶然生成されてしまうことがあります。

16進表記の文字列の生成ですら、「dead」「beef」「bad」「c0de」など、偶然生まれることがある単語はたくさんありますよね？ましてやBase36やBase64においては、すべてのアルファベットが符号に含まれますから、そのなかで不適切語となる単語が偶然生まれてしまうリスクも高くなってしまいます。

個人利用ならまだしも、他人に利用してもらうサービスでそういった不適切語、例えば「ass13」とか「wtf666」なんて文字列を含むIDが自動生成され、それがユーザーの目に触れるなんてことがあったら問題ですよね？

そういった不適切語を回避するためには、生成の際に不適切語が含まれているか確認して必要に応じて再生成する方法がよく取られますが、タイムスタンプの変換などエンコードされた文字列に数値の意味を持たせる場合、こういった再生成手法を取ることができません。

本記事では、こうした不適切語の発生を構造的に回避する英数字識別子符号化方式として、新たに設計したMarkovian-Base19/27 (MB1927) 方式を提案し、実装します。

背景

不適切語の回避のために現状よく用いられる方式として、辞書フィルタやパターンマッチングなどが挙げられますが、これらはいずれも一度符号化した後にそれを禁止する仕組みです。そのため、この仕組みを用いる場合、もとの数値・データとその符号化文字列の間で、相互にエンコード・デコードできない値が存在してしまうことになります。

また、既存の回避方法として、特定の文字を禁止する方法があります。例えばMicrosoftのプロダクトキーでは、ほかの文字と見間違うことの他にも、母音が含まれることによるリスクから以下の文字が使用されないことが多いです。

• 0, 1, 5 A, E, I, L, O, S, U, Z

しかし、このような特定の文字を一律で除外する手法にも限界があります。本記事では、符号化方式として、数値と符号化文字列が相互にエンコード・デコードできるという特徴を維持しつつ、数値をエンコードする時点で動的に除外文字を選択することで不適切語を一定度抑止する仕組みを考えました。

Markovian-Base19/27方式の設計過程

桁構造

ホスト名などで、先頭に数字が使えない環境を想定し、最上位桁を英文字のみとしています。
残りの桁については英数字とします。

全体から除外する文字の選定

欧米諸言語での不適切語について、特に危険度の高い語句には、母音としてa, i, o, uがeよりも多く含まれる傾向にあります。

• 英語での例: s**t → i / p**s → i / f**k → u / c**t → u / c**ks**ker → o,u,e / m**th*rf**ker → o,e,u / t*ts → i / *ssh**e → a,o,e / b**ch → i / d**n → a / b*st**d → a

  • 上の例でも、eのみからなる不適切語はなく、eはerやsilent eなど語の認識において重要でない位置についている

• ドイツ語、スペイン語、イタリア語などについても同様の傾向がある

• フランス語にはeのみからなる不適切語も同様に見られるが、それらは後述の方法で別途除去する

そのため、アルファベットのうちa, i, o, uをそもそも符号化文字セットから除くことで、これらの単語が生成されることを根本的に防ぐことができます。

次に、母音のLeet表記によるフィルタリング回避表記についてですが、o→0・i→1がe→3・a→4に比べて高頻度で出現する傾向があります。

したがって、数字のうち0, 1も符号化文字セットから除くことで、これらのLeet表記単語が生成されることを根本的に防ぐことができます。

結果として、MB1927方式で使われる文字セットは、23456789bcdefghjklmnpqrstvwxyzの30種類となります。

禁則連接ルールの設定

不適切語を回避するのに、母音の除去だけでは不十分です。母音を省略した形の不適切語や頭文字を取った不適切語、Leet表記を用いた不適切語など、想定されるケースは多岐にわたります。

そこで次に、そういった不適切語の構成部分となっている連接に着目します。

各桁ごとの情報量を均一化させるために、30種類のそれぞれの文字について、どの文字が連接すると不適切語が生成される危険性が高いかをそれぞれ3種類選び、その3種類は次に来てはいけない文字と定めます。この要領で左の文字を見てそこから危険性の高い連接となる3種類を除いた27種類を順次選択して符号化することで、27進法を維持しつつ特定の連接を除外することができます。

この方法は、各桁に使用できる文字が直前の文字に依存して変化するため、文字列の生成がマルコフ連鎖的な性質を持ちます。これにより、次に現れる可能性のある文字を制御することで、特定の連接を回避する構造が生まれます。

具体的な禁則連接は後述しますが、例えばbについては6, c, tを次に来てはいけない文字と定めます。

最上位桁の文字種と順序性

桁構造で述べた通り、最上位桁は英文字という前提にしています。ここで、桁数が異なる2つの符号の辞書順序性を維持するために、桁数が少ない方は英文字の最初の文字bでパディングすることができるものとします。

例えば、符号化された文字列としてepとdl3nを比較します。この時、もとの数値の大小関係はep$\lt$dl3nですが、辞書順の大小関係はep$\succ$dl3nとなってしまっています。これを、b埋めによってbbepとすることで、bbep$\lt$dl3n かつ bbep$\prec$dl3nとなり、数値の順序関係と符号の辞書順の順序関係を維持することができ、連番や数値的順序関係がある採番に対し、そのまま文字列比較によるソートや検索を行うことができます。

このとき、最上位桁の左にbが来る可能性があるということは、最上位桁にはcとtが来てはいけません。よって、最上位桁はb, c, tを除いたdefghjklmnpqrsvwxyzの19種類となります。

Markovian-Base19/27方式の詳細設計

名称

• 一般名称: Markovian-Base19/27
  • 左から順に符号化する際、直前の文字の種類のみに依存して次の文字に使える文字セットが決まるようなマルコフ的性質を持った、19進数と27進数の混合進法を意図
• 略称: MB1927
• 詳細名称: Markovian-Regulated 19-27-Mixed-Base System
• 日本語名称: マルコフ性19/27進法

数値範囲

• 0以上の整数において定義される
• 0の符号化をbと定め、桁揃え用の文字とする

最上位桁

• defghjklmnpqrsvwxyzの19種類

残りの桁

• 23456789bcdefghjklmnpqrstvwxyzの30種類の中から、一つ上の桁の文字に応じて特定の3種類を除外した27種類が動的に選択される

先行する文字	禁則とする連接文字	使用可能な文字
2	4, b, g	2356789cdefhjklmnpqrstvwxyz
3	k, p, x	23456789bcdefghjlmnqrstvwyz
4	r, s, t	23456789bcdefghjklmnpqvwxyz
5	4, 6, h	235789bcdefgjklmnpqrstvwxyz
6	6, 8, 9	23457bcdefghjklmnpqrstvwxyz
7	g, m, w	23456789bcdefhjklnpqrstvxyz
8	5, 8, 9	23467bcdefghjklmnpqrstvwxyz
9	n, t, y	23456789bcdefghjklmpqrsvwxz
b	6, c, t	2345789bdefghjklmnpqrsvwxyz
c	4, h, k	2356789bcdefgjlmnpqrstvwxyz
d	c, p, v	23456789bdefghjklmnqrstwxyz
e	e, m, x	23456789bcdfghjklnpqrstvwyz
f	e, k, w	23456789bcdfghjlmnpqrstvxyz
g	g, t, y	23456789bcdefhjklmnpqrsvwxz
h	8, e, s	2345679bcdfghjklmnpqrtvwxyz
j	9, e, q	2345678bcdfghjklmnprstvwxyz
k	k, r, s	23456789bcdefghjlmnpqtvwxyz
l	f, j, m	23456789bcdeghklnpqrstvwxyz
m	b, f, n	23456789cdeghjklmpqrstvwxyz
n	9, e, t	2345678bcdfghjklmnpqrsvwxyz
p	e, r, s	23456789bcdfghjklmnpqtvwxyz
q	e, n, v	23456789bcdfghjklmpqrstwxyz
r	d, k, t	23456789bcefghjlmnpqrsvwxyz
s	h, l, m	23456789bcdefgjknpqrstvwxyz
t	f, g, m	23456789bcdehjklnpqrstvwxyz
v	g, j, r	23456789bcdefhklmnpqstvwxyz
w	4, h, t	2356789bcdefgjklmnpqrsvwxyz
x	n, x, y	23456789bcdefghjklmpqrstvwz
y	4, e, s	2356789bcdfghjklmnpqrtvwxyz
z	b, d, g	23456789cefhjklmnpqrstvwxyz

回避される不適切語一覧

それぞれの禁則連接によって不適切語がブロックされ、生成されない単語が多くあります。
実際の単語例はここに挙げるのも憚られるため、リスト化したテキストファイルへのリンクを貼っておきます。

• 禁則連接リスト

連接の選定には、英語圏だけでなく多言語におけるラテン文字を用いた表記をできるだけ網羅したつもりです。簡易的な指標として、List of Dirty Naughty Obscene and Otherwise Bad Wordsに挙げられている単語とそのブロック数を表にしておきます。なお、以下記載語の母音省略形やLeet表記などの異表記を加味しない計算のため、文字種の時点でかなりの数が排除できているように見えますが、実際には異表記の多くは文字種による排除からはすり抜け、連接による排除で巻き取っている設計です。

言語	登録語数	文字種による排除語数	連接による排除語数	残存語数
英語	403	389	12	2
フランス語	91	83	6	2
オランダ語	190	181	8	1
イタリア語	168	166	1	1
フィンランド語	130	127	3	0
ハンガリー語	96	86	10	0
スペイン語	68	67	1	0
ドイツ語	66	65	1	0
ポーランド語	54	52	0	2
スウェーデン語	43	41	2	0
チェコ語	41	38	3	0
ノルウェー語	40	38	2	0
エスペラント語	37	35	2	0
日本語(ラテン文字音写後)	180	176	4	0
ロシア語(ラテン文字音写後)	151	145	5	1
ペルシャ語(ラテン文字音写後)	45	9	18	18
アラビア語(ラテン文字音写後)	38	13	12	13
中国語(ラテン文字音写後)	319	319	0	0
トルコ語	142	142	0	0
ヒンディー語	119	119	0	0
ポルトガル語	76	76	0	0
韓国語(ラテン文字音写後)	72	72	0	0
タイ語(ラテン文字音写後)	31	31	0	0
デンマーク語	20	20	0	0
フィリピン語	14	14	0	0

文字列の組み合わせ

エンコードとデコードには、全単射記数法(bijective notation)における、$n$桁以下の文字列が何個あるかの数え上げを応用します。

$n$桁の文字列の組み合わせは$19 \times 27^{n-1}$通りとなるため、$n$桁以下の文字列の個数は等比級数の和より $\frac{19 (27^n - 1)}{26}$ となります。

これを利用し、以下の流れで変換可能です。

エンコードの大まかな流れ

1. もとの数値から、エンコード結果が何桁の文字列で表現されるかを計算する
2. 決定された桁数より小さい桁数のすべての文字列の個数を引き、表現したい数がエンコード結果の桁数の範囲内のうち何番目の数かを特定する
3. 最上位以外は27進となるため、27進変換により各桁で何番目の文字を使うかの数値列を作成する
4. 作成した数値列を、最上位桁から順に使用できる文字セットを確認しながら文字を決定する

デコードの大まかな流れ

1. 文字列をもとに、最上位桁から順に使用できる文字セットを確認しながら、各桁で何番目の文字が使われているかの数値列を作成する
2. 最上位以外は27進となるため、数値列から27進変換により数値に変換する
3. 文字列の桁数より小さい桁数のすべての文字列の個数を加算する

Markovian-Base19/27方式の実装例

Pythonでのコード例

TOP_CHARS = "defghjklmnpqrsvwxyz"
TOP_BASE = 19
BODY_BASE = 27

ALLOWED_NEXT = {
    '2': "2356789cdefhjklmnpqrstvwxyz",
    '3': "23456789bcdefghjlmnqrstvwyz",
    '4': "23456789bcdefghjklmnpqvwxyz",
    '5': "235789bcdefgjklmnpqrstvwxyz",
    '6': "23457bcdefghjklmnpqrstvwxyz",
    '7': "23456789bcdefhjklnpqrstvxyz",
    '8': "23467bcdefghjklmnpqrstvwxyz",
    '9': "23456789bcdefghjklmpqrsvwxz",
    'b': "2345789bdefghjklmnpqrsvwxyz",
    'c': "2356789bcdefgjlmnpqrstvwxyz",
    'd': "23456789bdefghjklmnqrstwxyz",
    'e': "23456789bcdfghjklnpqrstvwyz",
    'f': "23456789bcdfghjlmnpqrstvxyz",
    'g': "23456789bcdefhjklmnpqrsvwxz",
    'h': "2345679bcdfghjklmnpqrtvwxyz",
    'j': "2345678bcdfghjklmnprstvwxyz",
    'k': "23456789bcdefghjlmnpqtvwxyz",
    'l': "23456789bcdeghklnpqrstvwxyz",
    'm': "23456789cdeghjklmpqrstvwxyz",
    'n': "2345678bcdfghjklmnpqrsvwxyz",
    'p': "23456789bcdfghjklmnpqtvwxyz",
    'q': "23456789bcdfghjklmpqrstwxyz",
    'r': "23456789bcefghjlmnpqrsvwxyz",
    's': "23456789bcdefgjknpqrstvwxyz",
    't': "23456789bcdehjklnpqrstvwxyz",
    'v': "23456789bcdefhklmnpqstvwxyz",
    'w': "2356789bcdefgjklmnpqrsvwxyz",
    'x': "23456789bcdefghjklmpqrstvwz",
    'y': "2356789bcdfghjklmnpqrtvwxyz",
    'z': "23456789cefhjklmnpqrstvwxyz",
}

def encodeMb1927(n: int) -> str:
    if not isinstance(n, int) or n < 0:
        raise ValueError("Must be a non-negative integer")
    if n == 0:
        return 'b'
    n -= 1
    digits = 1
    total = TOP_BASE
    while n >= total:
        digits += 1
        total += TOP_BASE * (BODY_BASE ** (digits - 1))
    prefix_total = TOP_BASE * (BODY_BASE ** (digits - 1) - 1) // (BODY_BASE - 1)
    n -= prefix_total
    indices = []
    for _ in range(digits):
        indices.insert(0, n % BODY_BASE)
        n //= BODY_BASE
    chars = []
    for i, idx in enumerate(indices):
        if i == 0:
            chars.append(TOP_CHARS[idx])
        else:
            prev = chars[-1]
            valid = ALLOWED_NEXT[prev]
            chars.append(valid[idx])
    return ''.join(chars)

def decodeMb1927(s: str) -> int:
    if s == 'b':
        return 0
    if not s:
        raise ValueError("Input must be a non-empty, valid string")
    indices = []
    for i, ch in enumerate(s):
        if i == 0:
            if ch not in TOP_CHARS:
                raise ValueError(f"Invalid first character: {ch}")
            indices.append(TOP_CHARS.index(ch))
        else:
            prev = s[i - 1]
            if prev not in ALLOWED_NEXT:
                raise ValueError(f"Previous character not found in transition map: {prev}")
            valid = ALLOWED_NEXT[prev]
            if ch not in valid:
                raise ValueError(f"Invalid character transition: {prev} → {ch}")
            indices.append(valid.index(ch))
    value = indices[0]
    for idx in indices[1:]:
        value = value * BODY_BASE + idx
    digits = len(s)
    prefix_total = TOP_BASE * (BODY_BASE ** (digits - 1) - 1) // (BODY_BASE - 1)
    return prefix_total + value + 1

javascriptでのコード例

const TOP_CHARS = "defghjklmnpqrsvwxyz";
const TOP_BASE = 19;
const BODY_BASE = 27;

const ALLOWED_NEXT = {
  '2': "2356789cdefhjklmnpqrstvwxyz",
  '3': "23456789bcdefghjlmnqrstvwyz",
  '4': "23456789bcdefghjklmnpqvwxyz",
  '5': "235789bcdefgjklmnpqrstvwxyz",
  '6': "23457bcdefghjklmnpqrstvwxyz",
  '7': "23456789bcdefhjklnpqrstvxyz",
  '8': "23467bcdefghjklmnpqrstvwxyz",
  '9': "23456789bcdefghjklmpqrsvwxz",
  'b': "2345789bdefghjklmnpqrsvwxyz",
  'c': "2356789bcdefgjlmnpqrstvwxyz",
  'd': "23456789bdefghjklmnqrstwxyz",
  'e': "23456789bcdfghjklnpqrstvwyz",
  'f': "23456789bcdfghjlmnpqrstvxyz",
  'g': "23456789bcdefhjklmnpqrsvwxz",
  'h': "2345679bcdfghjklmnpqrtvwxyz",
  'j': "2345678bcdfghjklmnprstvwxyz",
  'k': "23456789bcdefghjlmnpqtvwxyz",
  'l': "23456789bcdeghklnpqrstvwxyz",
  'm': "23456789cdeghjklmpqrstvwxyz",
  'n': "2345678bcdfghjklmnpqrsvwxyz",
  'p': "23456789bcdfghjklmnpqtvwxyz",
  'q': "23456789bcdfghjklmpqrstwxyz",
  'r': "23456789bcefghjlmnpqrsvwxyz",
  's': "23456789bcdefgjknpqrstvwxyz",
  't': "23456789bcdehjklnpqrstvwxyz",
  'v': "23456789bcdefhklmnpqstvwxyz",
  'w': "2356789bcdefgjklmnpqrsvwxyz",
  'x': "23456789bcdefghjklmpqrstvwz",
  'y': "2356789bcdfghjklmnpqrtvwxyz",
  'z': "23456789cefhjklmnpqrstvwxyz",
};

function encodeMb1927(n) {
  if (!Number.isInteger(n) || n < 0) throw new Error("Must be a non-negative integer");
  if (n === 0) return 'b';
  n--;
  let digits = 1, total = TOP_BASE;
  while (n >= total) {
    digits++;
    total += TOP_BASE * (BODY_BASE ** (digits - 1));
  }
  const prefix_total = Math.floor(TOP_BASE * (BODY_BASE ** (digits - 1) - 1) / (BODY_BASE - 1));
  n -= prefix_total;
  let indices = [];
  for (let i = 0; i < digits; i++) {
    indices.unshift(n % BODY_BASE);
    n = Math.floor(n / BODY_BASE);
  }
  let chars = [];
  indices.forEach((idx, i) => {
    if (i === 0) chars.push(TOP_CHARS[idx]);
    else chars.push(ALLOWED_NEXT[chars[i - 1]][idx]);
  });
  return chars.join('');
}

function decodeMb1927(s) {
  if (s === 'b') return 0;
  if (typeof s !== 'string' || s.length === 0) throw new Error("Input must be a non-empty, valid string");

  let indices = [];
  for (let i = 0; i < s.length; i++) {
    let idx;
    if (i === 0) {
      idx = TOP_CHARS.indexOf(s[i]);
      if (idx === -1) throw new Error(`Invalid first character: ${s[i]}`);
    } else {
      const prev = s[i - 1];
      const valid = ALLOWED_NEXT[prev];
      if (!valid) throw new Error(`Previous character not found in transition map: ${prev}`);
      idx = valid.indexOf(s[i]);
      if (idx === -1) throw new Error(`Invalid character transition: ${prev} → ${s[i]}`);
    }
    indices.push(idx);
  }

  let value = indices[0];
  for (let i = 1; i < indices.length; i++) {
    value = value * BODY_BASE + indices[i];
  }
  const digits = s.length;
  const prefix_total = Math.floor(TOP_BASE * (BODY_BASE ** (digits - 1) - 1) / (BODY_BASE - 1));
  return prefix_total + value + 1;
}

Markovian-Base19/27方式の変換例

具体的な数値の変換例

元の数値	MB1927エンコード結果
0	b
1	d
10	n
19	z
20	d2
28	db
29	dd
100	fz
532	zz
533	d22
1000	dmc
10000	rzp
14383	zzz
14384	d222
32767	dy8w
2147483647	hty6s2p
9223372036854775807	ejrfm3fpdk6qfs

数値→MB1927変換デモ

See the Pen 数値→MB1927 by 六葩くる (@muyuhira) on CodePen.

UNIXエポック秒→MB1927変換デモ

See the Pen UNIXエポック秒→MB1927 by 六葩くる (@muyuhira) on CodePen.

修正ユリウス日(MJD)→MB1927変換デモ

See the Pen 修正ユリウス日→MB1927 by 六葩くる (@muyuhira) on CodePen.

Markovian-Base19/27の派生方式: Markovian-Base27

MB1927の派生として、最上位桁に数字が来ることを許容する場合は27進数の変換方式になります。これの概略を示します。

名称

• 一般名称: Markovian-Base27
• 略称: MB27
• 詳細名称: Markovian-Regulated Base-27 System
• 日本語名称: マルコフ性27進法

数値範囲

• 0以上の整数において定義される
• 0の符号化を2と定め、桁揃え用の文字とする

最上位桁

• 356789cdefhjklmnpqrstvwxyzの26種類

残りの桁

• MB1927と同様

MB1927とMB27の比較

• 最上位桁が英文字になる広範用途としてはMB1927
• 計算の容易性と、データ圧縮率の微向上を図るならMB27
• いずれもバイナリデータの変換には向かない進数のため、与えられた数値の識別子への変換用途として有用

MB27への変換例

元の数値	MB27エンコード結果	MB1927エンコード結果
0	2	b
1	3	d
10	f	n
26	z	d8
27	32	d9
42	3j	dt
43	3l	dw
100	6r	fz
728	zz	d98
729	322	d99
1000	3d3	dmc
10000	kpd	rzp
19682	zzz	d998
19683	3222	d999
32767	3mym	dy8w
2147483647	8lpwgqd	hty6s2p
9223372036854775807	5cg6es7e5cxevd	ejrfm3fpdk6qfs

まとめ

提案した符号化方式は、順序関係と全単射関係を維持しながら、不適切語の回避を一定の割合で実現できるであろう算段です。GitHubの不適切語リスト(LDNOOBW)を多言語にわたって検査した結果と、禁則連接ルールによる削減効果をもとにした概算としては、英語圏において90～95%、欧州語圏において80～85%、アジア語圏において70～80%、世界全体で60～70%ほどの不適切語を自動的に排除することができる見積もりとなります。

具体的なユースケースとしては、以下の場面で有用となる符号化方式と考えます。

• サーバーのホスト名の採番 (例: d8c-server.example)
• ファイル名の短縮識別子 (例: en82mwr.png)
• URLのパス部分 (例: https://example.com/u/e2rf5lhkplqq)
• ログやセッションIDでの使用 (例: jlde3nyph)

ライセンスについて

本提案は、特定の著作物というよりも、構造的アイデアの1つであり、著作権の制約を設ける意図はありませんので、CC0ライセンスとして、自由に使用・改変・再利用していただいて構いません。