特殊な規則で作られた文字列からCSVを作成する関数を作りたい

Question

以下の規則で作られた文字列があります。

・ '[' , ']' によって入れ子に、もしくは並列に分けられます。
・'['のすぐ後には必ず大文字のアルファベットのみで構成される単語が付きます。これがtypeデータになります。
・typeデータの後にstrデータが続きます。typeデータとstrデータは必ず半角スペースで区切られます。
・strデータ内に '[' , ']' が含まれることはありません。strデータ内に'[' , ']'以外の記号（大文字小文字の英数字、カナ漢字、他の記号）が含まれることはあります。
・strデータが存在する入れ子の「深さ」をrankデータと定義します。あるstrデータの前にある '[' の数 と ']'の数 の差は、rankと等しいです。

たとえば、[A inu [B neko nyan [A tori] [AB kizi]] [B musi kabuto musi [CB taka]]]のような文字列です。

この文字列を解析して、CSVデータを作成する関数を作成したいです。

たとえば

[A inu [B neko nyan [A tori] [AB kizi]] [B musi kabuto musi [CB taka]]]

という文字列を解析すると、

rank,type,str
1,A , inu
2,B , neko nyan
3,A , tori
3,AB ,kizi
2,B , musi kabuto musi
3,CB ,taka

というCSVデータが作成されます。

このような動作を行う関数を教えてください。

自分でも文字列を一文字ずつ読み込んで、ifとpreg_matchで文字を判別しながら動作するものを作りましたが、圧倒的に遅いです。

array_walk_recursiveなどをうまく使えば高速に処理できるのかもしれませんが、自分では思いつきませんでした。

よろしくお願いします。

Answer 1

フォーマット的には正規表現や再帰的な処理も必要ないでしょうから、こんな感じでしょうか。

<?php

$str = "[A inu [B neko nyan [A tori] [AB kizi]] [B musi kabuto musi [CB taka]]]";

$tmp = explode("[", $str);

unset($tmp[0]);

$last_depth = null;
$last_end_count = 0;

echo "rank,type,str".PHP_EOL;
foreach($tmp as $key => $val){
        //$tag_end_count[$key] = mb_substr_count($val,"]");
        $current_end_count = mb_substr_count($val,"]");

        if(!$last_depth){
                $current_depth = 1;
        }else{

                $current_depth = $last_depth + 1 -  $last_end_count;
        }
        $last_depth = $current_depth;
        //出力
        echo  $current_depth.",";
        //rank以降のデータをスペースで分割し、最初のデータをtypeとする
        $data_tmp =  explode(" ",str_replace("]","",$val));
        echo $data_tmp[0].",";
        //typeを削除
        unset ($data_tmp[0]);
        //typeの後はスペースが必要？
        echo " ";

        echo implode(" ",$data_tmp);

        echo PHP_EOL;

        $last_end_count = $current_end_count;

}

$ php parse.php
rank,type,str
1,A, inu
2,B, neko nyan
3,A, tori
3,AB, kizi
2,B, musi kabuto musi
3,CB, taka

Comments

[salene05]

おおぉ　すごいです。
期待通りの結果が得られました。
本当にありがとうございます。

Answer 2

いやぁ…初めて見るフォーマットですね。
というわけで自作になるかと思います。

まずifはともかく、preg_matchは遅いです。
explodeだけで大部分はなんとかなりそうですね。
mb_substrやmb_strpos、mb_strlen等を駆使して取る事になるかと思います。

戦略
１．[を分割して配列を作る -> $a
２．$a[0]は[を確認していないのでBaseLv0、
$a[1]は[を通過しているのでBaseLv1、
…
３．配列$aをループで回しながら１つずつ値を取り出し、]で分割する -> $b
４．$bの要素数が1であれば、]は存在しなかった。
５．$bの要素数が2以上であれば、それ以降の要素はBaseLvを減算してから処理する

$word = "[A inu [B neko nyan [A tori] [AB kizi]] [B musi kabuto musi [CB taka]]]";

$down_lv = 0;
$results = array();
$results[] = array("rank", "type", "str");
$a = explode('[', $word);
foreach ($a as $base_lv => $up_word) {
  if (trim($up_word) === "") {
    continue;
  }
  $b = explode(']', $up_word);
  foreach ($b as $key => $core_word) {
    if ($key > 0) {
      $down_lv++; // 永続的にレベルダウンするので表示レベルが上がり続ける事はありません。
    }
    $target = trim($core_word);
    if ($target === "") {
      continue;
    }
    $left_word = mb_substr($target, 0, mb_strpos($target, ' '));
    $right_word = mb_substr($target, mb_strpos($target, ' ') + 1);
    $results[] = array(
      $base_lv - $down_lv,
      $left_word, // $targetを砕いて得られたType
      $right_word, // $targetを砕いて得られた文字列
    );
  }
}

// ここから出力して確認
foreach ($results as $seeds) {
  echo "{$seeds[0]}, {$seeds[1]}, {$seeds[2]}\n";
}
/*
rank, type, str
1, A, inu
2, B, neko nyan
3, A, tori
3, AB, kizi
2, B, musi kabuto musi
3, CB, taka
*/

ちなみにこの作戦だと、
全ての文字列を配列の中にぶち込んで作業するのでまぁまぁ富豪的で重いです。
本気でやるならmb_substrやmb_strpos、mb_strlenだけで最後までやり切るのが一番速いでしょうね。
やりたくは無いですが、回答者の回答の中で納得の速度が得られなければ試してみてください。

Comments

[miyabi-sun]

後から関数として切り出し安いように、$resultsに格納するようにしました。
まぁ、このせいでメモリを倍々で浪費する事になってます。
最初の文字列が数十MB以上…ヘタするとGB級のものだとすると本気で太刀打ち出来ないでしょう。

美しさ（変数名以外）はまぁまぁの自信作ですが、
速度はおそらくtanatさんのものより落ちるかと思います。
（10万件の同じデータで計測しても同じくらいでした。。。）

[salene05]

＞ifはともかく、preg_matchは遅いです。
なるほどです。str_splitで切り出して、preg_matchで判定～なんてやってましたorz

＞最初の文字列
たぶん、多いデータでも10kBいかないと思います。
ちなみにさっきまではstr_replaceとpreg_replaceで無理やりjsonに書き換えて、json_decode→配列操作～的な方法でも行けるかななんて考えたりしました。

とても参考になりました。ありがとうございました。

Answer 3

1文字ずつ読み込んで解析すればそんなに時間掛かりますか
[ と ] の数はひとしく、この2つはデータ中には出てこない。
データの先頭は必ず[ で始まるのだから、単純に、¥s*¥[
で分割した結果の個数がcsvの行数で、あとは、配列を先頭から
処理するとき、rank += 1 をやりつつ、文字列に ] が見つかるたびに
rank -= 1 を行う。
各文字列の先頭は、後続の半角スペースまで、type が確定する、その後文字列の末尾までが str になる。

hairetu, rank, index, ch, str、index2
で6つ変数があれば行けそうな気がします。

こんなルールのフォーマットは見たことがないのできっと独自の仕様なんでしょうね。
だとしたら、phpには、このフォーマットを解析可能な関数は無いと思いますよ。

ちなみに、このフォーマットの正式名称とかあるんですか。圧倒的に高速動作する見本はどのような言語でできてるんですか。

Comments

[salene05]

ありがとうございます。