ESP32 2432S028RとLVGLでMP3 Player - N分木(N-ary Tree)によるプレイリストの実装
はじめに
マルチコアの MCU やタッチパネル、マイクロ SD カード I/F、さらにはモノラルながらアンプも搭載した CYD で、これらをフル活用する MP3 プレイヤーを作成しています。
で、曲を管理するプレイリストには、SD カードから拾ったオーディオファイルのパスを文字列として配列に入れていました。
/MP3/Against The Current/Gravity/Gravity.m4a
/MP3/Against The Current/Gravity/Talk.m4a
/MP3/Against The Current/Gravity/...
/MP3/Against The Current/Gravity/Nada Sousou.m4a
/MP3/Against The Current/Gravity/Imasugu Kiss Me.m4a
/MP3/Against The Current/Past Lives/Strangers Again.m4a
/MP3/Against The Current/Past Lives/The Fuss.m4a
/MP3/Against The Current/Past Lives/...
/MP3/Against The Current/Past Lives/NIJI.m4a
/MP3/Against The Current/Past Lives/Eyes Like Guns.m4a
/MP3/ONE OK ROCK/DETOX/NASTY.m4a
/MP3/ONE OK ROCK/DETOX/Dystopia.m4a
/MP3/ONE OK ROCK/DETOX/...
/MP3/ONE OK ROCK/DETOX/C.U.R.I.O.S.I.T.Y..m4a
/MP3/ONE OK ROCK/DETOX/The Pilot ＜ _3.m4a
/MP3/ONE OK ROCK/Eye Of The Storm/Eye Of The Storm.m4a
/MP3/ONE OK ROCK/Eye Of The Storm/Stand Out Fit In.m4a
/MP3/ONE OK ROCK/Eye Of The Storm/...
/MP3/ONE OK ROCK/Eye Of The Storm/Can't Wait.m4a
/MP3/ONE OK ROCK/Eye Of The Storm/The Last Time.m4a
/MP3/ONE OK ROCK/Nicheシンドローム/Never Let This Go.m4a
/MP3/ONE OK ROCK/Nicheシンドローム/完全感覚Dreamer.m4a
/MP3/ONE OK ROCK/Nicheシンドローム/...
/MP3/ONE OK ROCK/Nicheシンドローム/未完成交響曲.m4a
/MP3/ONE OK ROCK/Nicheシンドローム/Nobody's Home.m4a
/MP3/Superfly/Amazing/彩り (Mr.Children).m4a
/MP3/Superfly/Amazing/果てない空 (嵐).m4a
/MP3/Superfly/Amazing/...
/MP3/Superfly/Amazing/たしかなこと (小田和正).m4a
/MP3/Superfly/Amazing/メロディー (玉置浩二).m4aこれでは明らかにアーティスト名やアルバム名が重複し、メモリを無駄に消費しています。この無駄をなくすことが今回のお題です。
すぐに思いつくのは、tree コマンドの出力と同様の 木構造 でデータを管理することです。
tree コマンドの出力例
MP3
├── Against The Current
│ ├── Gravity
│ │ ├── Gravity.m4a
│ │ ├── ...
│ │ └── Imasugu Kiss Me.m4a
│ └── Past Lives
│ ├── Strangers Again.m4a
│ ├── ...
│ └── Eyes Like Guns.m4a
├── ONE OK ROCK
│ ├── DETOX
│ │ ├── NASTY.m4a
│ │ ├── ...
│ │ └── The Pilot ＜ _3.m4a
│ ├── Eye Of The Storm
│ │ ├── Eye Of The Storm.m4a
│ │ ├── ...
│ │ └── The Last Time.m4a
│ └── Niche シンドローム
│ ├── Never Let This Go.m4a
│ ├── ...
│ └── Nobody's Home.m4a
└── Superfly
└── Amazing
├── 彩り (Mr.Children).m4a
├── ...
└── メロディー (玉置浩二).m4a中でも「Ｎ分木」(N-ary tree) の実装を今回の目標としました。
「N-ary tree」の「ary」って何？と思った方はコチラ 👈
Google に「Ｎ分木」の英訳「N-ary tree」の「ary」とは何ですか？ と尋ねました。
「N-ary tree」の「ary」は、「～の次数」や「～の要素を持つ」という意味で、N個の要素を持つことを表しています。具体的には、N分木の場合、各ノードが最大N個の子ノードを持つことを意味します。 「ary」は、接尾辞として、ラテン語の「-arius」に由来し、「～に関わる」、「～の性質を持つ」という意味合いを持ちます。この場合、「N個の要素を持つ」という性質を表すために使用されています。例えば、「binary tree」 (二分木) では、各ノードが最大2個の子ノードを持ちます。 つまり、「N-ary tree」の「ary」は、「N個の子ノードを持つ」というツリーの構造的な特徴を指し示す言葉として使われています。
また ラテン語の「-arius」 は、名詞を形容詞にする働きがあるようで、budget（予算）→budgetary（予算上の）、fragment（断片）→fragmentary（断片的な、不完全な）、revolution（革命）→revolutionary（革命的な）などと同じ成り立ちのようです。
ライブラリの調査
世の中にも同様のニーズはあるハズで、見つけたのが次のライブラリです。
標準テンプレートライブラリ（Standard Template Library）のように、指定したデータ型をノード内に持つ木を作成できる C++11 に則ったライブラリです。
ドキュメント には、木の巡回やノードの追加／削除はもちろん、部分木の追加／削除や２つの異なるツリーの比較やマージなどができるとあり、かなりの汎用性を持っています。
なかなか魅力的なライブラリですが、今回の件には少々オーバスペック気味です。いつか使うかもしれないライブラリとしてストックしておき、今回はアルゴリズムとコーディングの勉強を兼ね、自作することにしました。
今回の要件
予めオーディオファイルが保存された SD カードを読み込むだけで、ファイルやフォルダの追加／削除機能などは必要なく、前述のライブラリに比べてかなりシンプルになるハズです。
要件としては、次の２つを設定しました。
木の大きさや管理するデータ長
SD カードの中身は、図２のように構造化され、木の高さや幅は予め決められないとします。また ID3 タグ 仕様によれば、それぞれの文字列長を規定できるかもしれませんが、各ノードに保存される文字列は任意の長さとします。
プレイリスト GUI との関係性
図３のように、末端の葉ノードに紐付いた曲のリストをプレイリストとして表示することを想定します。即ち、葉ノードに対するアーティスト名やアルバム名、ファイルパスが容易に、かつ高速に探索できなければなりません。またプレイリストは、シャッフル再生用に容易に並べ替えられる必要があります。
コードの基本形
アルゴリズムとデータ構造の学習支援サイト GeeksforGeeks の Tree Data Structure には様々な木構造が、そこそこ具体的な C++ のコードと共に解説されています。中でも今回は、Introduction to Generic Trees (N-ary Trees) の Better Approach に掲載された次のＮ分木用のクラス定義を元にしました。
#include <vector>
class Node {
public:
int data;
std::vector<Node*> children;
Node(int data) {
this->data = data;
}
};上記と SD カードを再帰的に 深さ優先探索 する SD ライブラリの例題関数 listDir() とを組み合わたコードを作ってみました。ただし、末端の葉ノードからルートまで辿れるよう、親ノードへのポインタ Node* parent を追加しています。
次のサンプルコードは、ファイル名とクラス名が合ってませんし、assert() でお茶を濁している箇所がありますが、ご勘弁を…
tree.hpp
#ifndef _TREE_HPP_
#define _TREE_HPP_
#include <string>
#include <vector>
#include <exception>
#include <assert.h>
#include <string.h>
#include "FS.h"
/*----------------------------------------------------------------------
* クラスの定義
*----------------------------------------------------------------------*/
class Node {
public:
Node* parent; // 親ノードへのポインタ
std::string name; // フォルダ名 or ファイル名
std::vector<Node*> children; // 子ノードの集合
Node(const char * name, Node * parent = NULL) {
this->parent = parent;
this->name = name;
}
~Node() {
for (auto &n : this->children) {
delete n;
}
this->children.clear();
this->name.clear();
}
// 新しいノードを生成し、子ノードの集合に追加する
Node* append(const char * name) {
Node *node = new Node(name, this);
assert(node);
try {
this->children.push_back(node);
} catch (const std::exception &e) {
assert(false); // e.what()
}
return node;
}
private:
// 拡張子をチェック
bool check_mp3(const char *path) {
const char* ext[] = {".mp3", ".m4a", ".wav"};
for (int i = 0; i < sizeof(ext) / sizeof(ext[0]); i++) {
if (strcmp(&path[strlen(path) - strlen(ext[i])], ext[i]) == 0) {
return true;
}
}
return false;
}
// ファイルシステムを巡回する
void scan_node(File &dir, Node *node) {
for (File entry = dir.openNextFile(); entry; entry = dir.openNextFile()) {
const char *name = entry.name();
if (entry.isDirectory()) {
scan_node(entry, node->append(name));
}
else if (check_mp3(name)) {
node->append(name);
}
entry.close();
}
}
public:
// ファイルツリーを構築する
void scan_file(File &dir) {
scan_node(dir, this);
}
private:
void print_node(Node * node, int indent) {
++indent;
for (auto &n : node->children) {
for (int j = 0; j < indent; j++) { Serial.print(" "); }
Serial.printf("%s (%d)\n", n->name.c_str(), n->children.size());
if (n->children.size()) {
print_node(n, indent);
}
}
}
public:
// ツリーを巡回し、ノードの情報を出力する
void print_tree(void) {
Serial.printf("%s (%d)\n", this->name.c_str(), this->children.size());
print_node(this, 0);
}
};
#endif // _TREE_HPP_N_Ary_Tree1.ino
#include "SD.h"
#include "tree.hpp"
#define ROOT_FOLDER "/MP3/" // ルートフォルダ
void setup() {
Serial.begin(115200);
while (millis() < 1000);
if (!SD.begin()) {
Serial.println("Can't initialize SD.");
return;
}
File dir = SD.open(ROOT_FOLDER);
if (!dir) {
Serial.println("Can't open " ROOT_FOLDER ".");
return;
}
Node *root = new Node(ROOT_FOLDER);
root->scan_file(dir);
root->print_tree();
delete root;
dir.close();
Serial.println("end");
}
void loop() {}
ただこのままだと、末端の葉ノードが木に埋め込まれるため、別途プレイリストとの紐付けが必要です。さらに曲のファイルパスを得るには、Node* parent を辿りながら文字列を逆順に繋げるか、一旦ルートまで辿った後に戻りながら文字列を連結する必要があり、あまり効率が良くありません。
改良版のコード
前章の基本形に少し手を加え、木の根（ルート）から目的の葉ノードまで順方向に探索できるように改良します。
アルゴリズムの概要
-
構築済みのツリーにおいて、葉ノードに整数のキーを０から順に割り当てます（図５）。指定したキーを持つ葉ノードを探索することがゴールです。
-
親ノードのキーには、子ノードに割り当てられたキーの最大値を割り当てます（図６）。
-
指定のキーを持つ葉ノードを探索するには、ルートから出発し、
ノードのキー ≧ 指定のキーが成立するノードを順に辿ります（図７）。辿り着いた先が葉ノードであれば、それが目的のノードとなります。
前章の基本形に対するこの方法のメリットは、葉ノードとプレイリストの間が整数値の「キー」で紐付けられるだけなので、疎結合1 となることです。
また探索のアルゴリズムは、前述のＮ分木に対して 平衡二分探索木 の一種である Ｂ木 や 赤黒木 の探索の考え方に近いです。探索にかかる計算量は、枝ノードの探索中は O(log n)、葉ノードに辿り着いてからは O(n) となります。
今回の場合、最後の O(n) の n は、１枚のアルバムに含まれる曲数、即ち高々十数曲程度なので、気にするほどではないと踏んでます 🧐
サンプルコード
次の２つは、このアルゴリズムを実現するコードです。
tree.cpp に定義された静的変数は、探索中に発見したフォルダ名を順に繋いてファイルパスを保持するためのグローバル変数です。リエントラント なコードじゃなくなるのででイケてませんが、発見したパスを再帰関数の引数と戻り値で引き回すのがイヤだったので…。
今回の場合、プレイリストのオブジェクトは高々１つしか存在しないので、問題ナシとしています（言い訳です、ハイ 😅）
tree.hpp
#ifndef _TREE_HPP_
#define _TREE_HPP_
#include <string>
#include <vector>
#include <exception>
#include <assert.h>
#include <string.h>
#include "FS.h"
/*----------------------------------------------------------------------
* クラスの定義
*----------------------------------------------------------------------*/
class Node {
private:
static bool found; // ノード探索用フラグ
static std::string path; // ファイルパスの探索結果
static uint16_t n_leafs; // 末端の葉ノード数
public:
uint32_t key; // 各ノードに付与されるキー
std::string name; // フォルダ名 or ファイル名
std::vector<Node*> children; // 子ノードの集合
Node(const char * name) {
this->name = name;
}
~Node() {
this->children.clear();
for (auto &n : this->children) {
delete n;
}
this->children.clear();
this->name.clear();
}
// 末端の葉ノード数
const size_t size(void) {
return n_leafs;
}
// 新しいノードを生成し、子ノードの集合に追加する
Node* append(const char * name) {
Node *node = new Node(name);
assert(node);
try {
this->children.push_back(node);
} catch (const std::exception &e) {
assert(false); // e.what()
}
return node;
}
private:
// 拡張子をチェック
bool check_mp3(const char *path) {
const char* ext[] = {".mp3", ".m4a", ".wav"};
for (int i = 0; i < sizeof(ext) / sizeof(ext[0]); i++) {
if (strcmp(&path[strlen(path) - strlen(ext[i])], ext[i]) == 0) {
return true;
}
}
return false;
}
// ファイルシステムを巡回する
void scan_node(File &dir, Node *node) {
for (File entry = dir.openNextFile(); entry; entry = dir.openNextFile()) {
const char *name = entry.name();
if (entry.isDirectory()) {
scan_node(entry, node->append(name));
}
else if (check_mp3(name)) {
node->append(name);
}
entry.close();
}
}
// 各ノードにキーを振る
void traverse_node(Node *node) {
for (auto &n : node->children) {
if (n->children.size()) {
traverse_node(n);
} else {
n->key = n_leafs++;
}
}
node->key = n_leafs - 1;
}
public:
// ファイルツリーを構築する
void scan_file(File &dir) {
scan_node(dir, this);
n_leafs = 0;
traverse_node(this);
}
private:
// 指定キーを持つ葉ノードを見つける
bool find_node(Node * node, int key) {
for (auto &n : node->children) {
// 指定のキーが含まれる？
if (n->key >= key) {
// さらに子ノードがある？
if (n->children.size()) {
path.append(n->name).append("/");
if (find_node(n, key)) {
return found;
}
}
// 目的のキーに到達
else {
assert(n->key == key);
path.append(n->name);
found = true;
return found;
}
}
}
return found;
}
public:
// 指定のキーを持つ葉ノードを探索し、ファイルパスを返す
std::string find_path(int key) {
found = false;
path = this->name;
if (find_node(this, key)) {
return path;
} else {
return "";
}
}
private:
void print_node(Node * node, int indent) {
++indent;
for (auto &n : node->children) {
for (int j = 0; j < indent; j++) { Serial.print(" "); }
Serial.printf("%s (%d)\n", n->name.c_str(), n->children.size());
if (n->children.size()) {
print_node(n, indent);
}
}
}
public:
// ツリーを巡回し、ノードの情報を出力する
void print_tree(void) {
Serial.printf("%s (%d)\n", this->name.c_str(), this->children.size());
print_node(this, 0);
}
};
#endif // _TREE_HPP_tree.cpp
#include "tree.hpp"
/*----------------------------------------------------------------------
* 静的メンバ変数の定義
*----------------------------------------------------------------------*/
bool Node::found; // ノード探索用フラグ
std::string Node::path; // ファイルパスの探索結果
uint16_t Node::n_leafs; // 末端の葉ノード数またファイルパスの探索は、前章 N_Ary_Tree1.ino の root->print_tree(); を次のコードで置き換えます。
N_Ary_Tree2.ino（ファイルパス探索のコードのみ）
const int n = root->size();
for (int key = 0; key < n; key++) {
std::string path = root->find_path(key);
Serial.printf("%3d: %s\n", key, path.c_str());
}探索性能の比較
基本形と改良版で、１曲当たりの探索時間の平均値を比較してみました。SD カードの中身は、アーティスト数 5、アルバム数 10、曲数は 130 です。
| １曲当たりの探索時間 - SD ライブラリ | １曲当たりの探索時間 - SdFat ライブラリ | |
|---|---|---|
| 基本形 | 38.3 [μs] | 48.8 [μs] |
| 改良版 | 15.3 [μs] | 14.5 [μs] |
どちらもプレイリストの GUI スクロール時に問題となる値ではありませんが、改良の効果アリという結果になりました 👍
ようやく…
ココまで辿り着きました。
16GB の microSD カードには千数百曲程度が収まるハズなので、お次はプレイリストの編集用 GUI の作成です。全体のツリーから部分木を切り出し、幾つかのプレイリストとして保存するような実装とする予定です。とっても面倒なコーディングとなりそうなので、重い腰が中々上がりません 😮💨
また 基本動作編 では CYD に外部スピーカーを繋ぎましたが、Bluetooth 化もしたいですし…
ということで、まだまだ時間がかかりそうです 🍄
-
疎結合（そけつごう）とは、システムやソフトウェアの構成要素間の依存関係が弱い状態を指します。これにより、各要素が独立して動作しやすくなり、変更や拡張が容易になるというメリットがあります。反対に、要素間の依存関係が強い状態は密結合と呼ばれます。（by Google AI） ↩