Zenn
🍇

BudouXのJava実装をPHPに移植する

2023/09/27に公開
PHP
#
budoux
tech

BudouXというGoogle社が公開しているライブラリがあって、数日前に紹介記事が発表されて話題になっていました。

https://developers-jp.googleblog.com/2023/09/budoux-adobe.html

日本語は分かち書きをしない言語ですが、Webなどで行折り返しをするとき文字数や字幅だけで改行してしまうと不自然になってしまうことがあります。プログラマにとって著名な例はあなたとJAVA, 今すぐダウンロー
ドでしょうか。

むかしからHTML標準に触れていた方にとってはお馴染みでしょうか、HTMLには<wbr>: 改行可能要素 - HTML: ハイパーテキストマークアップ言語 | MDNという要素があり、折り返しのときに改行できる位置を指示できるものでしたが、いかんせん手作業で入れるのは面倒なので存在は知られているが実際に使うことはほとんどないものという認識がありました。suikawiki: wbr 要素 (HTML)でもまとめられている通り、実に歴史のあるHTML要素ではあります。

さて、今回新たに公開されたものではなく2年くらい前に発表されていたと思いますが、ChromeやAndroidにも組み込まれて自然に使われるようになったというのは喜ばしいことです。

さて、BudouXは機械学習の成果を利用したものでありながらランタイムに特殊な依存がなく言語中立に設計されています。そんなものなので2年の間に誰かがPHPに移植したりしてるかなと思ったのですが特にそんなことはなかったので昼間に寝て中途半端に眠くない深夜にエイヤっとやってみました。

https://github.com/zonuexe/budoux-php

……とりあえずパーサーだけ。元リポジトリにはJava実装が含まれていて、Parserクラスだけで200行未満なので1時間もあれば移植できてしまいました。

既にPackagistでも公開していて、以下のコマンドでダウンロードできます。

composer require zonuexe/budoux

以下のように使えます。

<?php
require __DIR__ . '/vendor/autoload.php';

$parser = \Budoux\Parser::loadDefaultJapaneseParser();

// HTMLとして展開したい場合
echo implode('<wbr>', $parser->parse('あなたとJAVA, 今すぐダウンロード'));

LaravelではBladeの拡張を参考にディレクティブを追加してあげると使いやすいんじゃないでしょうか。たぶん。

Javaコードの移植

で、ここからはどうやって実装していったかを書いていきましょう。

PHPとJavaは似てるか似てないかでいうとちょっと似てるのでコード移植の題材としてはかなりやりやすい部類ですが、言語機能が同じかというと全然違うので両者の違いというのは当然に意識しておく必要があります。

ファイル冒頭部

/*
 * Copyright 2023 Google LLC
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *     https://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */

package com.google.budoux;

import com.google.gson.Gson;
import com.google.gson.JsonIOException;
import com.google.gson.JsonSyntaxException;
import com.google.gson.reflect.TypeToken;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.Reader;
import java.lang.reflect.Type;
import java.nio.charset.StandardCharsets;
import java.util.ArrayList;
import java.util.List;
import java.util.Map;
import java.util.Optional;

こうなります。

<?php

/*
 * Copyright 2023 Google LLC
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *     https://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */

declare(strict_types=1);

namespace Budoux;

use function array_is_list;
use function array_key_last;
use function array_map;
use function array_sum;
use function array_values;
use function file_get_contents;
use function json_decode;
use function mb_strlen;
use function strlen;

Javaでやっているクラスのインポートみたいなのは一切無視して構いません。PHPの名前空間は今回は単にBudouxとしておきましょう。ちゃんとPSR-4に則って考えるならzonuexe\Budouxとかになるのですが。

use function は見慣れてない方はまったく見慣れてないと思うのですが、PHPでパフォーマンス最適化するためのおまじないだと考えておいてください。これが何を意味するのかはZendEngineにえこひいきされる標準関数たち (前篇)に書きました。

クラス定義

/**
 * The BudouX parser that translates the input sentence into phrases.
 *
 * <p>You can create a parser instance by invoking {@code new Parser(model)} with the model data you
 * want to use. You can also create a parser by specifying the model file path with {@code
 * Parser.loadByFileName(modelFileName)}.
 *
 * <p>In most cases, it's sufficient to use the default parser for the language. For example, you
 * can create a default Japanese parser as follows.
 *
 * <pre>
 * Parser parser = Parser.loadDefaultJapaneseParser();
 * </pre>
 */
public class Parser {
  private final Map<String, Map<String, Integer>> model;

  /**
   * Constructs a BudouX parser.
   *
   * @param model the model data.
   */
  public Parser(Map<String, Map<String, Integer>> model) {
    this.model = model;
  }
  • JavadocにはHTMLが書けますが、phpDocumentorはMarkdownを認識してくれることになってます
  • クラス可視性の概念はPHPにはないので public class ではなく単に class にします
  • PHPのプロパティに立派な型定義構文はないのでシンプルにします
    • プロパティ宣言としてはJavaの Map を array に置き換えます
    • PHPDocで詳細な型 @var array<string, array<string, int>> を書きましょう
  • むかしのPHPもクラス名と同じ名前のメソッドを定義するとコンストラクタとして機能しましたが、いまはそうではないので __construct() にします
    • 現代PHPではコンストラクタプロモーションが使えるのでさらに単純化できます。
/**
 * The BudouX parser that translates the input sentence into phrases.
 *
 * You can create a parser instance by invoking `new Parser(model)` with the model data you
 * want to use. You can also create a parser by specifying the model file path with
 * `Parser.loadByFileName(modelFileName)`.
 *
 * In most cases, it's sufficient to use the default parser for the language. For example, you
 * can create a default Japanese parser as follows.
 *
 *     $parser = Parser::loadDefaultJapaneseParser();
 *
 */
class Parser
{
    /**
     * Constructs a BudouX parser.
     */
    public function __construct(
        /** @var array<string, array<string, int>> */
        private array $model,
    ) {
    }

すごくすっきりしましたね。幸先いいぞ。

ファクトリメソッド

  /**
   * Loads the default Japanese parser.
   *
   * @return a BudouX parser with the default Japanese model.
   */
  public static Parser loadDefaultJapaneseParser() {
    return loadByFileName("/models/ja.json");
  }

Javaはクラス内のメソッドを関数のように呼び出せますが、PHPはメソッドと関数が共存しはっきりと区別するので、暗黙的にメソッドが呼ばれることなどはなく self::loadByFileName() として呼び出す必要があります。

    /**
     * Loads the default Japanese parser.
     */
    public static function loadDefaultJapaneseParser(): Parser
    {
        return self::loadByFileName(__DIR__ . '/../budoux/models/ja.json');
    }

ロードメソッド

  /**
   * Loads a parser by specifying the model file path.
   *
   * @param modelFileName the model file path.
   * @return a BudouX parser.
   */
  public static Parser loadByFileName(String modelFileName) {
    Gson gson = new Gson();
    Type type = new TypeToken<Map<String, Map<String, Integer>>>() {}.getType();
    InputStream inputStream = Parser.class.getResourceAsStream(modelFileName);
    try (Reader reader = new InputStreamReader(inputStream, StandardCharsets.UTF_8)) {
      Map<String, Map<String, Integer>> model = gson.fromJson(reader, type);
      return new Parser(model);
    } catch (JsonIOException | JsonSyntaxException | IOException e) {
      throw new AssertionError(e);
    }
  }

JavaではGsonでJSONデータを型付けしてデコードしています。かっこいいですね。PHPでそういうことをやってもいいのですが、めんどくさいのでガン無視しましょう。

    /**
     * Loads a parser by specifying the model file path.
     *
     * @param string $modelFileName the model file path.
     * @phpstan-param non-empty-string $modelFileName
     * @return Parser a BudouX parser.
     */
    public static function loadByFileName(string $modelFileName): Parser
    {
        $content = file_get_contents($modelFileName);
        assert($content !== false);

        /** @var array<string, array<string, int>> $model */
        $model = json_decode($content, true);

        return new self($model);
    }

出、出〜 @var型付奴〜〜〜〜ｗｗｗｗｗ

ここをくそまじめに型検査してもいいのですが、JSONファイルはリポジトリに同梱していて通常はそれが置き換えられることはないので、今日はこんなもんで勘弁しておいてやる。

スコア計算

  /**
   * Gets the score for the specified feature of the given sequence.
   *
   * @param featureKey the feature key to examine.
   * @param sequence the sequence to look up the score.
   * @return the contribution score to support a phrase break.
   */
  private int getScore(String featureKey, String sequence) {
    return Optional.ofNullable(this.model.get(featureKey))
        .map(group -> group.get(sequence))
        .orElse(0);
  }

いいですね、Optionalが使われていてテンションが上がります。PHPでもこれやりたい！ ……なのですが、PHPではもっと簡単に扱えてしまいます。

    /**
     * Gets the score for the specified feature of the given sequence.
     *
     * @param string $featureKey the feature key to examine.
     * @param string $sequence the sequence to look up the score.
     * @return int the contribution score to support a phrase break.
     */
    private function getScore(string $featureKey, string $sequence): int
    {
        return $this->model[$featureKey][$sequence] ?? 0;
    }

実際のところJava版でやってることはこれだけです。PHPもJavaっぽいと言われますが、こういうところはLLらしく、きっちりシンプルに書けていいですね。

パースメソッド (冒頭)

これまでの部分より量があるので、メソッド全体ではなく分けて見ましょう。

  /**
   * Parses a sentence into phrases.
   *
   * @param sentence the sentence to break by phrase.
   * @return a list of phrases.
   */
  public List<String> parse(String sentence) {
    if (sentence.isEmpty()) {
      return new ArrayList<>();
    }
    List<String> result = new ArrayList<>();
    result.add(String.valueOf(sentence.charAt(0)));
    int totalScore =
        this.model.values().stream()
            .mapToInt(group -> group.values().stream().mapToInt(Integer::intValue).sum())
            .sum();

これもPHPに書き換えてみましょう。

    /**
     * Parses a sentence into phrases.
     *
     * @param string $sentence the sentence to break by phrase.
     * @return string[] a list of phrases.
     * @phpstan-return list<string>
     */
    public function parse(string $sentence): array
    {
        if (strlen($sentence) === 0) {
            return [];
        }

        $result = [
            mb_substr($sentence, 0, 1, 'UTF-8'),
        ];

        $totalScore = array_sum(array_map(array_sum(...), array_values($this->model)));
  • 最初に空文字列だったら空リストを返して終っています
  • 次に最終的な結果を格納するresult変数を作ります
    • sentence.charAt(0)は文字列の先頭の文字をとるものです
    • PHPで $sentence[0] のようにアクセスすることも可能ですが、これはUTF-8文字ではなく先頭バイトしかとれません
    • mb_strlen()関数で切り出すことでコードポイント単位で扱えるようになります
  • totalScoreは毎回再計算する必要ない… 気もしますが今回はこのまま置いておきましょう
    • そのうち暇なときに、ちゃんとパフォーマンス計測したいですね

うむPHP、同じことをやってるのにいい感じにスカスカになっていいですね！

ついでに言っておくとJavaのStringクラスはUTF-16で、PHPには内部文字コードのような概念はないのですが事実上UTF-8だけを扱うことが現代では暗黙的な前提になっているので、そのように処理します。ここについて語ると長くなるので次の機会に譲ります。

パースメソッド (計算)

    for (int i = 1; i < sentence.length(); i++) {
      int score = -totalScore;
      if (i - 2 > 0) {
        score += 2 * this.getScore("UW1", sentence.substring(i - 3, i - 2));
      }
      if (i - 1 > 0) {
        score += 2 * this.getScore("UW2", sentence.substring(i - 2, i - 1));
      }
      score += 2 * this.getScore("UW3", sentence.substring(i - 1, i));
      score += 2 * this.getScore("UW4", sentence.substring(i, i + 1));
      if (i + 1 < sentence.length()) {
        score += 2 * this.getScore("UW5", sentence.substring(i + 1, i + 2));
      }
      if (i + 2 < sentence.length()) {
        score += 2 * this.getScore("UW6", sentence.substring(i + 2, i + 3));
      }
      if (i > 1) {
        score += 2 * this.getScore("BW1", sentence.substring(i - 2, i));
      }
      score += 2 * this.getScore("BW2", sentence.substring(i - 1, i + 1));
      if (i + 1 < sentence.length()) {
        score += 2 * this.getScore("BW3", sentence.substring(i, i + 2));
      }
      if (i - 2 > 0) {
        score += 2 * this.getScore("TW1", sentence.substring(i - 3, i));
      }
      if (i - 1 > 0) {
        score += 2 * this.getScore("TW2", sentence.substring(i - 2, i + 1));
      }
      if (i + 1 < sentence.length()) {
        score += 2 * this.getScore("TW3", sentence.substring(i - 1, i + 2));
      }
      if (i + 2 < sentence.length()) {
        score += 2 * this.getScore("TW4", sentence.substring(i, i + 3));
      }
      if (score > 0) {
        result.add("");
      }
      result.set(result.size() - 1, result.get(result.size() - 1) + sentence.charAt(i));
    }
    return result;
  }

とても地道に計算してますね！

        $length = mb_strlen($sentence, 'UTF-8');

        for ($i = 1; $i < $length; $i++) {
            $score = -$totalScore;
            if ($i - 2 > 0) {
                $score += 2 * $this->getScore("UW1", mb_substr($sentence, $i - 3, 1, 'UTF-8'));
            }
            if ($i - 1 > 0) {
                $score += 2 * $this->getScore("UW2", mb_substr($sentence, $i - 2, 1, 'UTF-8'));
            }
            $score += 2 * $this->getScore("UW3", mb_substr($sentence, $i - 1, 1, 'UTF-8'));
            $score += 2 * $this->getScore("UW4", mb_substr($sentence, $i, 1, 'UTF-8'));
            if ($i + 1 < $length) {
                $score += 2 * $this->getScore("UW5", mb_substr($sentence, $i + 1, 1, 'UTF-8'));
            }
            if ($i + 2 < $length) {
                $score += 2 * $this->getScore("UW6", mb_substr($sentence, $i + 2, 1, 'UTF-8'));
            }
            if ($i > 1) {
                $score += 2 * $this->getScore("BW1", mb_substr($sentence, $i - 2, 2, 'UTF-8'));
            }
            $score += 2 * $this->getScore("BW2", mb_substr($sentence, $i - 1, 2, 'UTF-8'));
            if ($i + 1 < $length) {
                $score += 2 * $this->getScore("BW3", mb_substr($sentence, $i, 2, 'UTF-8'));
            }
            if ($i - 2 > 0) {
                $score += 2 * $this->getScore("TW1", mb_substr($sentence, $i - 3, 3, 'UTF-8'));
            }
            if ($i - 1 > 0) {
                $score += 2 * $this->getScore("TW2", mb_substr($sentence, $i - 2, 3, 'UTF-8'));
            }
            if ($i + 1 < $length) {
                $score += 2 * $this->getScore("TW3", mb_substr($sentence, $i - 1, 3, 'UTF-8'));
            }
            if ($i + 2 < $length) {
                $score += 2 * $this->getScore("TW4", mb_substr($sentence, $i, 3, 'UTF-8'));
            }
            if ($score > 0) {
                $result[] = '';
            }

            $result[array_key_last($result)] .= mb_substr($sentence, $i, 1, 'UTF-8');
        }

        assert(array_is_list($result));

        return $result;
    }

PHP版はまたmb_substr()関数で切り出してきます。ここもなんか最適化できそうな感じがしますが、当てずっぽうで対処するのはよくないのでこのままにしておきましょう。JavaのString.substring()が始点と終点を渡すのに対して、PHPのmb_substr()では始点と切り出す長さを渡すのが異なるので、それぞれ適切に書き換えてやる必要があります。

元コードのsentence.length()に相当するのはmb_strlen($sentence, 'UTF-8')ですが… これを毎回計算するのは明らかに無駄なので、$lengthという変数に一度だけ入れておきます。「推測するな計測せよ」とはよく言いますが、このくらい自明なら特にパフォーマンス計測するまでもなくやってしまいます。

PHPStanで型付けする上で特筆すべきことは$result[array_key_last($result)]というコードが混じっていることで list<string> が array<int, string> に化けてしまうことですが… これはちょっとめんどいので assert(array_is_list($result)); で型を list<string> に引き戻してやることができます。

translateHTMLString

  /**
   * Translates an HTML string with phrases wrapped in no-breaking markup.
   *
   * @param html an HTML string.
   * @return the translated HTML string with no-breaking markup.
   */
  public String translateHTMLString(String html) {
    String sentence = HTMLProcessor.getText(html);
    List<String> phrases = parse(sentence);
    return HTMLProcessor.resolve(phrases, html);
  }

パスします！ PHPの標準関数ではDOMが扱いにくすぎる、DOMDocumentという標準クラスはあるが、いろんな制約があってつらい、今回の要件で同じように処理するのはちょっとつらい… ということで未実装。

まとめ

JavaとPHPの絶妙な距離感が説明できて楽しかったですね。Javaに比べてPHPの機能不足のようなものを感じないでもありませんが、PHPもなかなかどうしてシンプルにまとまっていて侮れないものです。

……元のBudouXの話から逸れてしまいましたが、基本部のソースコードはこの記事で抜萃したものだけでほぼ全部です。これだけのシンプルな実装できちんと動くのはすごいですね。この処理をサーバーサイドでやるべきかクライアントサイドでやるべきか、はたまたブラウザ実装に任せるかは議論があるところだと思いますが……、選択肢ができたのはとても素晴しいですね！

Discussion