ひらがなをローマ字に変換するアルゴリズムを考える

こんにちは。

普段何気なく使っているローマ字入力、たとえば「ねっこ」と入力するだけでも「nekko, necco, neltuko, neltuco, nextuko, nextuco, neltsuko, neltsuco, nextsuko, nextsuco」と10パターンの入力方法があります。

今日はこのローマ字入力パターンを全て求めるアルゴリズムを考えてみます。

このアルゴリズムは再帰を使うので、文字数が増えると計算量が累乗的に増えます。
アルゴリズムの専門ではないので、もっと早くできるやり方や、バグ、変なコード教えてください！

ローマ字入力の歴史

ローマ字を考えるのに、歴史について簡単に調べてみました。

先ほど、「ねっこ」の入力パターンを列挙したのですが、ローマ字入力が色々な組み合わせで入力できるのには、日本語をローマ字で表現しようとした先人たちのおかげであることがわかりました👼

一般的によく聞くものとして、「ヘボン式」と「訓令式」があります。
ヘボン式ローマ字入力表を小さい頃にもらった記憶がありますが、この方式はアメリカ人の宣教師が和英辞典に使った書き方が元になっています。これを元に「羅馬字会」が定めたものが「ヘボン式」です。元が和英辞典だったことから、英語の発音を基準にローマ字に変換しています。
これに対して、日本語の発音や表記規則を元に定められたものが、「訓令式」です。

他にも「〜式」と呼ばれるようなローマ字表記法がいくつもあり、コンピュータを作成したメーカーが実装する、IMEによって色々な入力方法が乱立されている状況となりました。
これを統一するために、ローマ字入力の変換方式を定めた日本の企画が、2000年に定められたJIS X 4063:2000です。その後コンピューターに搭載されるIMEが統一されて行き、コンピュータごとの入力方法の差が少なくなったことで、2010年に廃止されました。

こんな歴史から、今のローマ字入力は、主に「ヘボン式」と「訓令式」の2パターンで入力できるものに落ち着いていました。

ローマ字入力のパターンを考える

早速アルゴリズムを考えるために「ねっこ」を例に考えてみます。
「ね」を入力する時には「ne」を最初に入力することが確定します。その後に「っ」の入力方法次第で条件が分岐していき以下のようになります。

ne
├── ltu
│   ├── ko
│   └── co
├── ltsu
│   ├── ko
│   └── co
├── xtu
│   ├── ko
│   └── co
├── xtsu
│   ├── ko
│   └── co
├── kko
└── cco

「っ」を入力する時に、「ltu」のように単体で入力する場合と、「kko」のように、次のひらがなの最初の文字を重ねて入力する2パターンが存在することがわかります。

これをJavaScriptのオブジェクト的に表現すると、以下のようになります。
romaをそのオブジェクトが持つローマ字のプロパティ、その子に当たる入力パターンをchildren配列として表現します。

{
  roma: 'ne',
  children: [
    {
      roma: 'ltu',
      children: [
        {
          roma: 'ko'
        }, {
          roma: 'co',
        }
      ]
    }, {
      roma: 'xtu',
      children: [
        {
          roma: 'ko',
        }, {
          roma: 'co',
        }
      ]
    }, {
      roma: 'ltsu',
      children: [
        {
          roma: 'ko',
        }, {
          roma: 'co',
        }
      ]
    }, {
      roma: 'xtsu',
      children: [
        {
          roma: 'ko',
        }, {
          roma: 'co',
        }
      ]
    }, {
      roma: 'kko',
    }, {
      roma: 'cco',
    }
  ]
}

とりあえず、こんな感じのツリー構造を作れれば良さそうなので、作ってみます。

また、この時に「ん」が文章内に存在するケース、たとえば「んと」と入力したいような場合は、「nnto, nto」と「n」の入力を省略できるのでこちらも考慮してみます。

作る

扱うデータ

まずは、ツリー構造内で一つの入力パターンを表現するためのClassを用意します。
romaが入力パターン、childrenがそれ以下の入力パターン、parentが自分の親にあたる入力パターンです。

export class Roman {
  roma: string
  children: Roman[] = []
  parent: Roman | undefined

  constructor (roma: string) {
    this.roma = roma
  }

  addChild (roman: Roman): void {
    this.children.push(roman)
    roman.parent = this
  }
}

このClassをツリー構造にしていきます。

基本的な入力パターン

ローマ字入力をする上で、単体で入力パターンが確定するものを最初にリストアップします。

config.ts

const KEY_CONFIGS: KeyConfigs = [
  {
    key: "あ",
    origins: ["a"],
  },
  {
    key: "い",
    origins: ["i", "yi"],
  },
  {
    key: "う",
    origins: ["u", "wu", "whu"],
  },
  ...以下略
]

このkeyのひらがなから入力可能な、originsをツリー構造に追加していくイメージです。

全パターンはこちらhttps://github.com/2ndPINEW/HiraganaParser/blob/develop/src/core/config.mts

ツリー構造を作る

先ほど定義したKEY_CONFIGSからツリー構造を作ってみます。

コード内で行っていることは、各コメントを参照してください。

parser.ts

import { KEY_CONFIGS } from "./config";

export const hiraganaToRomans = (hiraganas: string) => {
  // ツリー構造の起点となる空文字のツリーを作成
  const startRoman = new Roman("");
  addNextChild(hiraganas, startRoman);

  return startRoman;
};

const addNextChild = (remainingHiraganas: string, parentRoman: Roman) => {
  // 空文字の場合は最後の文字なので何もしない
  if (!remainingHiraganas) {
    return;
  }

  // キーから始まる設定を探す
  const matchKeyConfigs = KEY_CONFIGS.filter((keyConfig) =>
    remainingHiraganas.startsWith(keyConfig.key)
  );
  // キーから始まる設定の、ローマ字の組み合わせを子ノードとして追加する
  matchKeyConfigs.forEach((matchKeyConfig) => {
    matchKeyConfig.origins.forEach((origin) => {
      const nextRoman = new Roman(origin);
      parentRoman.addChild(nextRoman);
      const nextHiraganas = remainingHiraganas.slice(matchKeyConfig.key.length);
      addNextChild(nextHiraganas, nextRoman);
    });
  });
};

これで、KEY_CONFIGSとして定義した一番基本的なパターンはツリー構造にすることができました。

「ん」と「っ」を考慮する

まず「ん」を一つにできる条件は、次の入力が「n, a, i, u, e, o, y」から始まっていなくて、次の入力があることです。
この条件を満たすかどうかを判定するisArrowOneNInputという関数を作ります。
この関数に、残りのひらがなを渡したときにtrueであれば、「n」1文字で「ん」と入力ができるので、先ほどのaddNextChild関数の中に条件分岐を追加します。

次に、「っ」を重ねて入力可能になる条件は、次の入力が「n, a, i, u, e, o, y」から始まらず、次の入力があることです。
この条件を満たす場合は、duplicateFirstLetterフラグを立てた状態でaddNextChild関数を再度呼ぶようにします。この時に、「っ」を取り除いたそれ以降の文字列を残りのひらがなとして渡すことで、次のノードを追加する処理の部分で、最初の文字を重ねた状態で追加します。

コメントにて間違いを報告いただいたので修正しました。
ご指摘ありがとうございます！！

この二つのことを考慮してコード全文を書き直してみます。

import { KEY_CONFIGS } from "./config.mjs";

export const hiraganaToRomans = (hiraganas: string) => {
  // ツリー構造の起点となる空文字のツリーを作成
  const startRoman = new Roman("");
  addNextChild(hiraganas, startRoman);

  return startRoman;
};

const addNextChild = (
  remainingHiraganas: string,
  parentRoman: Roman,
  duplicateFirstLetter?: true
) => {
  // 空文字の場合は最後の文字なので何もしない
  if (!remainingHiraganas) {
    return;
  }

  // 「っ」の時はその次の文字を重ねたやつもいける
  if (isAllowDuplicateFirstLetter(remainingHiraganas)) {
    const nextHiraganas = remainingHiraganas.slice(1);
    addNextChild(nextHiraganas, parentRoman, true);
  }

  // 「ん」の時は次がnから始まらないならn一個で入力ができるので追加する
  if (isAllowOneNInput(remainingHiraganas)) {
    const nextRoman = new Roman("n");
    parentRoman.addChild(nextRoman);
    const nextHiraganas = remainingHiraganas.slice(1);
    addNextChild(nextHiraganas, nextRoman);
  }

  // キーから始まる設定を探す
  const matchKeyConfigs = KEY_CONFIGS.filter((keyConfig) =>
    remainingHiraganas.startsWith(keyConfig.key)
  );
  // キーから始まる設定の、ローマ字の組み合わせを子ノードとして追加する
  matchKeyConfigs.forEach((matchKeyConfig) => {
    matchKeyConfig.origins.forEach((origin) => {
      // 重ねて入力するフラグが立っている場合は、最初の文字を重ねて入力する
      const nextRoman = duplicateFirstLetter
        ? new Roman(origin[0] + origin)
        : new Roman(origin);
      parentRoman.addChild(nextRoman);
      const nextHiraganas = remainingHiraganas.slice(matchKeyConfig.key.length);
      addNextChild(nextHiraganas, nextRoman);
    });
  });
};


const isAllowDuplicateFirstLetter = (remainingHiraganas: string): boolean => {
  return remainingHiraganas.startsWith('っ')
      && !isNextStartWithN(remainingHiraganas)
      && hasNextHiraganas(remainingHiraganas)
      && !isNextStartWithConsonant(remainingHiraganas)
}

// 残りのひらがなてきに、「n」一つで「ん」を入力できるかどうか
const isAllowOneNInput = (remainingHiraganas: string): boolean => {
  // 「ん」から始まってない場合はだめ
  if (!remainingHiraganas.startsWith('ん')) {
    return false
  }

  return remainingHiraganas.startsWith('ん')
      && !isNextStartWithN(remainingHiraganas)
      && hasNextHiraganas(remainingHiraganas)
      && !isNextStartWithConsonant(remainingHiraganas)
}

const hasNextHiraganas = (remainingHiraganas: string): boolean => {
  const nextHiraganas = remainingHiraganas.slice(1)
  return !!nextHiraganas
}

/** 次の文字がNから始まっているかどうか */
const isNextStartWithN = (remainingHiraganas: string): boolean => {
  const nextHiraganas = remainingHiraganas.slice(1)
  if (!nextHiraganas) return false

  const matchKeyConfigs = KEY_CONFIGS.filter(keyConfig => nextHiraganas.startsWith(keyConfig.key))
  return matchKeyConfigs.some(matchKeyConfig => 
    matchKeyConfig.origins.some(origin => origin.startsWith('n'))
  )
}

/** 次の文字が子音から始まっているかどうか */
const isNextStartWithConsonant = (remainingHiraganas: string): boolean => {
  const nextHiraganas = remainingHiraganas.slice(1)
  if (!nextHiraganas) return false

  const matchKeyConfigs = KEY_CONFIGS.filter(keyConfig => nextHiraganas.startsWith(keyConfig.key))
  return matchKeyConfigs.some(matchKeyConfig =>
    matchKeyConfig.origins.some(origin => isConsonant(origin[0]))
  )
}

const isConsonant = (char: string): boolean => {
  return ['a', 'i', 'u', 'e', 'o', 'y'].includes(char)
}

export class Roman {
  roma: string;
  children: Roman[] = [];
  parent: Roman | undefined;

  constructor(roma: string) {
    this.roma = roma;
  }

  addChild(roman: Roman): void {
    this.children.push(roman);
    roman.parent = this;
  }
}

これで「ねっこ」のような小さい「っ」を入力する場合、「んと」のような「n」一つで「ん」を入力する場合、どちらも正しくツリー構造にできるようになりました。

最後に

このツリー構造を後ろから辿っていって、ローマ字入力の組み合わせにすれば、ローマ字入力のパターンにできますし、そのまま前から辿って行けばタイピングゲームなどに使えます。
このコードは半年ほど前に考えたコードだったのですが、今見てもこれよりシンプルなコードを思いつかなかったので、記事にしてみました。良い再帰ライフを🎉

リポジトリ

このリポジトリは、タイピングゲーム向けに作っていたので、入力済みのひらがなの位置を判別できるようなコードが入っていたり、記事で触れた内容より機能が多くなっています。

https://github.com/2ndPINEW/HiraganaParser