2017年6月12日月曜日

[Java] 文字列を区切り文字を含んで分割する(StringTokenizer・正規表現)


猫と一緒にガジェットライフ♪ムチャです。

前回の続きです。
そもそもこの話はとある面接で出された問題が元になっています。それは、
「与えられた文字列を指定の区切り文字で分割し、逆順にした上で区切り文字も含めて再構成する」
という問題でした。与えられた時間は10分くらいで、渡されたPCがカーソル飛びまくるし固まるしで(言い訳)完全には解けなかったので反省をこめて書いています(;´∀`)




文字列を特定の区切り文字で分割する

Javaで文字列を分割する方法はいくつかありますが、複数の区切り文字・区切り文字を含めて取得するとなるとちょっと難しいです。

StringTokenizerを使う

Javaの最初のバージョンからあるのがStringTokenizerクラスです。
このクラスはコンストラクタ引数の3つ目が区切り文字を返すかどうかのフラグになっていて、trueを渡すと区切り文字自体もトークンとして返してくれます。

String s = "abc:efg:hij:klmn:opq";

//3つ目の引数にtrueを渡すと、区切り文字もトークンとして取得できる
//・・・が、区切り文字は1つしか指定できない
StringTokenizer t = new StringTokenizer(s, ":", true);
List<String> list = new ArrayList<>();

//Iterableを実装してないので拡張for文は使えず・・・
while(t.hasMoreTokens()){
  list.add(t.nextToken());
}
System.out.println(list);

出力結果
[abc, :, efg, :, hij, :, klmn, :, opq]

区切り文字自体も1つの要素としてリストに入っています。
区切り文字は複数文字を指定できます。その場合文字列全体ではなく、各文字がそれぞれ区切り文字として扱われます。

ただこのクラス、APIドキュメントに以下の記述があります。
StringTokenizerは、互換性を維持する目的で保持されているレガシー・クラスであり、新規コードでは使用が推奨されていません。この機能の使用を考えているなら、Stringのsplitメソッドまたはjava.util.regexパッケージを代わりに使用することをお薦めします。
というわけでString#splitでやってみましょう。


String#splitでやる

String#splitは引数が一つだけ、区切り文字として使う正規表現を渡します。
区切り文字を含むかどうかは指定できません。
単純に以下のように書くともちろん区切り文字は入りません。
String s = "abc:efg:hij:klmn:opq";
List<String> list = Arrays.asList(s.split(":"));
System.out.println(list);
出力結果
[abc, efg, hij, klmn, opq]

さあどうしましょうか。
正規表現は文字にマッチングするだけではありません。位置にマッチングする構文もあります。

※ちなみに区切り文字が複数ある場合は、文字クラス"[]"を使えばできます。
("[,.:]"など)

■ 先読み、後読み
それぞれ肯定と否定があり、APIドキュメントPatternクラスに書いてある定義を並べてみると以下のようになっています。
  • (?=X) X、幅ゼロの肯定先読み
  • (?!X) X、幅ゼロの否定先読み
  • (?<=X) X、幅ゼロの肯定後読み
  • (?<!X) X、幅ゼロの否定後読み
これだけだと全く意味が分かりません┐(´ー`)┌
この辺の記事が詳しいです。
正規表現の先読み/後読みを「絞り込み」と理解してみる - Qiita

「先読み」は指定したパターンが直後に来る位置にマッチし、「後読み」は直前に来る位置にマッチします。この位置のことは「アンカー」と呼ぶようです。
否定の場合はパターンが来ない時にマッチします。

例えばウィキペディアのとあるページからこんな↓データを用意して、
RGM-79[G] 陸戦型ジム(陸戦用先行量産型ジム)
RGM-79[G] ジム・スナイパー
RGM-79BD-1 ブルーディスティニー1号機
RGM-79[E] 先行量産型ジム 宇宙戦仕様
RGM-79E 初期型ジム(宇宙用ジム ルナツー仕様)
RGM-79 前期量産型ジム前期
RGM-79 前期量産型ジム後期型
RGM-79S ジム指揮官機[2]
RGM-79GL ジム・ライトアーマーコマンド[要出典]
RGM-79 ジム(ガンダム サンダーボルト版)
RGM-79/GH ガンダムヘッド
:
こんな感じ↓で肯定先読みを使って「RGM-79」の後にFが続くものをリストアップしてみると、
Path p = Paths.get(ClassLoader.getSystemResource(&quot;gm.txt&quot;).toURI());
Pattern ptn = Pattern.compile(&quot;RGM-79(?=F)&quot;);

//Files#linesはファイルを開いてStreamを得られるJava8の新メソッド
//StreamはAutoCloseableを実装しているのでtry-with-resource構文が使えます
try(Stream&lt;String&gt; lines = Files.lines(p)){
    lines.filter(s -&gt; ptn.matcher(s).find())
        .forEach(System.out::println);
}

実行結果
RGM-79F 陸戦用ジム
RGM-79F デザート・ジム
RGM-79F 装甲強化型ジム 
RGM-79FP ジム・ストライカー
RGM-79FP ジム・ストライカー改
RGM-79FP-S1 ジム・ストライカー改〈メタル・スパイダー〉
RGM-79FC ストライカー・カスタム
こんな感じになります。

で、これを使って区切り文字を含めて文字列を分割するにはどうすればよいか。
指定したパターンが直前、または直後に来る位置で区切ればよいわけです。
パターンは「(?<=X)|(?=X)」です。先読み、後読みを「|」で論理和にしてやります。
String s = "abc:efg:hij:klmn:opq";

List<String> list = Stream.of(s.split("(?<=:)|(?=:)"))
                        .collect(Collectors.toList());
System.out.println(list);

実行結果
[abc, :, efg, :, hij, :, klmn, :, opq]

StringTokenizerを使ったものよりだいぶスッキリしました。


■ もっと単純に・・・「境界正規表現エンジン」
そんなややこしいものを使わなくてももっと簡単なのがありました。
それが「境界正規表現エンジン」としてAPIドキュメントに載っています。
^ 行の先頭
$ 行の末尾
\b 単語境界
\B 非単語境界
\A 入力の先頭
\G 前回のマッチの末尾
\Z 最後の行末記号がある場合は、それを除く入力の末尾
\z 入力の末尾
行頭の「^」や行末の「$」は使ったことがある方も多いと思います。
その中に単語境界「\b」というのがあるじゃないですか!

String s = "abc:efg:hij:klmn:opq";

List<String> list = Stream.of(s.split("\\b"))
                        .collect(Collectors.toList());
System.out.println(list);
実行結果
[abc, :, efg, :, hij, :, klmn, :, opq]

今までの苦労はいったい・・・(´ー`)

ただこれだと区切り文字が2文字以上続いていたらだm・・・いや+使えばいいか。

String s = "abc:efg::hij|/:klmn:,.opq";

List<String> list = Stream.of(s.split("\\b+"))
                        .collect(Collectors.toList());
System.out.println(list);

実行結果
[abc, :, efg, ::, hij, |/:, klmn, :,., opq]

"+"は「直前の文字の1回以上の繰り返し」を表します。
これなら区切り文字が連続していても大丈夫です。


■ 「単語境界」とはなにか
じゃあこの"\b"で何がヒットするのでしょうか。

APIドキュメントには特に記載がありません。
ググってみると、単語構成文字"\w"(→[a-zA-Z_0-9])以外、"\W"と同じと書かれていたりもしますが、Javaでも”\W"はAPIドキュメントにそのように書いてあってその通りにヒットします。[a-zA-Z_0-9]以外というのはその通り日本語もその中には含まれないので非単語文字となります。

しかし、"\b"では日本語も単語として扱われて境界にはなりません。

なのでソースを追ってみます。
String#splitは正規表現メタキャラクタが全く無い場合単純な分割をしますが、そうで無い場合はPatternおよびMatcherクラスを使います。
Patternクラスの内部クラスにPattern.Nodeというクラスがあり、これを継承した様々なクラスが用意されています。多分各種メタキャラクタに対応しているようです(未確認)。
Pattern#escapeメソッドで"\"に続く文字を見て該当するNodeのサブクラスを生成しています。

その中にPattern.Boundというクラスがあり、これが"\b"のときに生成されています。

Nodeのサブクラスはmatchメソッドをオーバーライドして固有の実装をしているようですが。Boundではそこから呼ばれるisWordメソッドにほぼ答えがあります。

boolean isWord(int ch) {
  return useUWORD ? UnicodeProp.WORD.is(ch) : (ch == '_' || Character.isLetterOrDigit(ch));
}

三項演算子の条件になっているuseUWORDはPattern#compileの第2引数にPattern.UNICODE_CHARACTER_CLASSを指定した場合にフラグが立つのですが、多分普段はあまり使わないでしょう(?)ということで、後半を見ます。

そうするとアンダースコアか、Character.isLetterOrDigit(int)がtrueのときとなるので、そちらを見ます。
APIドキュメントだと「指定された文字(Unicodeコード・ポイント)が汎用文字または数字かどうかを判定します。」としか書いてなくてやはり分からないのでソースを。

public static boolean isLetterOrDigit(int codePoint) {
return ((((1 << Character.UPPERCASE_LETTER) |
  (1 << Character.LOWERCASE_LETTER) |
  (1 << Character.TITLECASE_LETTER) |
  (1 << Character.MODIFIER_LETTER) |
  (1 << Character.OTHER_LETTER) |
  (1 << Character.DECIMAL_DIGIT_NUMBER)) >> getType(codePoint)) & 1) != 0;
}

何をやってるかよくわからないかもしれませんが、getTypeでどの汎用カテゴリかを取得して、各フラグをシフトしつつorを取ってマスクを作り、列挙された定数のどれかに一致していればtrueを返すようになっています。

今度は「汎用カテゴリ」という言葉が出てきました。
Unicodeの汎用カテゴリというものの分かりやすい説明が見つからず、まあそういう物があるのでしょう(投げやり)。
各カテゴリにどういう文字が含まれているかは、JavaのAPIドキュメントよりMicrosoftの.Net Frameworkのドキュメントの方が少し詳しく書いてあります。
UnicodeCategory 列挙型 (System.Globalization)
  • UPPERCASE_LETTER
  • LOWERCASE_LETTER
  • TITLECASE_LETTER
  • MODIFIER_LETTER
  • OTHER_LETTER
  • DECIMAL_DIGIT_NUMBER
UPPER/LOWERは大文字、小文字ですね。DECIMAL_DIGIT_NUMBERはそのまま0~9の数字ですが、日本語の全角数字を含む様々な言語の数字を表す文字が含まれています・・・と思ったら、ローマ数字の”Ⅲ”などはLETTER_NUMBERという別カテゴリになっています。うーん。

TITLECASEは、もともと論文などの表題において全ての単語の1文字目を大文字にする書き方を指します(英語の論文とか書いたことない雑魚修士とバレるw)が、一部大文字でも小文字でもない別の字形が割り当てられているようです。対象は31文字しかなく、日本語はもちろん普通に英語の論文書くにも使わなそうな気がします。
List of Unicode Characters of Category “Titlecase Letter”

MODIFIER_LETTERは修飾文字で、上付き文字みたいな一つ前の前の文字を修飾するものです。あまりなじみが薄そうと思いきや、日本語でも"々"や"ゞ"などがこのカテゴリに入っています。
List of Unicode Characters of Category “Modifier Letter”

そしてほとんどの文字はOTHER_LETTERに入っています・・・って結局分からんやんけ!
文字数にして15000とかあるので、どうしたもんでしょう。
List of Unicode Characters of Category “Other Letter”

結論としては、対象とする区切り文字が"\b"でヒットするかをテストして、いけそうなら"\b"でいけばいいということになるでしょうか。
ここまでで力尽きました_:(´ཀ`」 ∠): _

■ 余談
ちなみに、汎用カテゴリにはSURROGATEというのもあります。もしかしてサロゲートペアの文字は単語境界として判定してしまう・・・?

String s = "あああ𩸽ううう|おおお"; //𩸽(ほっけ)→\ud867,\ude3d

List<String> list = Stream.of(s.split("\\b"))
                      .collect(Collectors.toList());
System.out.println(list);

出力結果
[あああ𩸽ううう, |, おおお]

分割されませんでした。Charactor#getType(int)は"𩸽"のコードポイント\u29e3dを渡すと5(→OTHER_LETTER)を返します。
じゃあSURROGATEは何だというと、上位または下位サロゲートコードだけ渡したときにSURROGATE(19)が返るようです。



めでたしめでたし・・・?

これで今回は終わり・・・という前に、「指定した文字だけを区切りとして扱いつつ、区切り文字が続く場合はそこを区切らずに、区切り文字も含めて取得したい」というときはどうすればよいでしょう。
(そんなケースねえよ!というのは置いといて・・・)

それで区切り文字を含みつつ、かつ区切り文字が連続する場合を除いて分割するには、否定/肯定の先読み/後読みを全て使って・・・

String delim = ";:,";
String str = "あおいうふぇ abc.lxu,:;fewag'ow$fowajfw#fg-あfaoik,,oijgr:freagjfoajg |afewag,,,,,,aaa";
Stream.of(str.split("(?<=[" + delim + "])(?![" + delim + "])|(?<![" + delim + "])(?=[" + delim + "])"))
  .forEach(System.out::println);
実行結果
あおいうふぇ abc.lxu
,:;
fewag'ow$fowajfw#fg-あfaoik
,,
oijgr
:
freagjfoajg |afewag
,,,,,,
aaa

正規表現がえらいことになっていますが、区切り文字の結合している部分を除いて単純な文字列にすると以下のようになります。
"(?<=[;:,])(?![;:,])|(?<![;:,])(?=[;:,])"

中央に"|"が入っていて、左右どちらかがマッチすればよいとなっています。

前半は直前に文字クラス内の文字があり、かつ直後に文字クラス内の文字がない位置にマッチ=区切り文字の開始位置。
後半は逆に直前に文字クラス内の文字が無く、かつ直後に文字クラス内の文字がある位置にマッチ=区切り文字の終了位置。
となります。

いや、ここまでやる必要があるか、そんな状況があるかどうかと言えばまず無いでしょうけど(;´∀`)
正規表現が複雑だからか、対象文字列が長かったり何度も繰り返すとけっこう遅かったです。もし実運用で使う場合はご注意ください。


リストを逆順にする

もう一つやることがああります。
ListならばCollections#reverseに渡すと破壊的に入れ替えてくれます。
(新しいリストを返すのでは無く、引数で渡したリストの内容を書き換える)
List<String> result = ....
Collections.reverse(result);

配列の場合、Arraysクラスにはreverseがありません。
Arrays#asListListにしてしまうのが早そうです。

Streamでも逆順にする操作がありません。sotredメソッドはありますが、自然順序に従ってソートされてしまうので、Stringなら辞書順になってしまいます。
とりあえず思いついたのは、Comparatorとして常に-1を返すものを指定すること。
Stream.of("あ","い","う","え","お")
  .sorted((a,b) -> -1)
  .forEach(System.out::println);
実行結果
お
え
う
い
あ

いいのかな(;´∀`)
Streamにする前もしくはcollectメソッドでリストにしてからではなく、Streamのまま逆順にしたいときはこの方法しかなさそうです。今のところJava9でもreverseは無さそうです。


おしまいのひとこと

だいぶ長くなってしまいましたが、解けない問題があるのが嫌なので突き詰めてみました。
実際に使うことはないかもしれませんが、一つ分かったのはString#splitは引数が以下の条件を満たす場合、正規表現ではなく単純な文字分割を行うということです。
  • 1文字で、正規表現のメタキャラクタ(".$|()[{^?*+\\")以外
  • 2文字で、最初が"\"、次が英数字以外かつ(上位サロゲートコード最小値以下または下位サロゲートコード最大値以上=D800-DFFFの範囲外)
2つ目がなぞいですね・・・"\"+アルファベットの組み合わせも正規表現でいろいろな意味を表すのでそれを除外しているにしては範囲が広いです。
まあ区切り文字を2文字にすることもあまりないと思うので考えなくて良いでしょう。
何が言いたいかというと、複数の文字列を一旦1つにまとめておく(CSVのように)とき、1つ目の文字以外を使った方がパフォーマンス上有利と思われるということです。

長々とお付き合いありがとうございました。
それではみなさまよきガジェットライフを(´∀`)ノ


▼こちらの記事もどうぞ

▼ブログを気に入っていただけたらRSS登録をお願いします!
▼ブログランキング参加中!応援よろしくお願いします。

スポンサーリンク