世界中のすべての本をISBN-Space上に可視化する

 (phiresky.github.io)
2 ポイント 投稿者 GN⁺ 2025-02-02 | 1件のコメント | WhatsAppで共有
  • Anna’s Archiveが扱う1億冊以上の書籍データを1画面で探索するには、ISBNという限られた識別子空間を地図に変換するアプローチが必要になる
  • ISBN13は978-/979-接頭辞と最後のチェックサムを除くと、約20億スロットの1次元空間であり、国や出版社の範囲が接頭辞単位で割り当てられている
  • 単純な行単位の配置やHilbert curveではISBNの構造が見えにくくなる可能性があるため、10進数の桁を2D座標へ移すBookshelf-Curveを使う
  • 地図タイルはPNGとJSONの静的ファイルとして提供され、WebGL/GLSLシェーダーが発行年、所蔵率、データセット比較、出版社強調といったレンダリングとフィルタリングを即座に処理する
  • ThreeJS、React、MobX、react-threejs-fiberベースの静的フロントエンドとして実装されており、大量のテキスト描画とズーム移動の性能最適化が実用性を左右する

ISBN空間を可視化対象にした理由

  • 図書館は古くから人類の知識を集めてきており、デジタル時代には特定の基準を満たす著作物を包括的に収集することが可能になりうる
  • シャドーライブラリの1つであるAnna’s Archiveには、1億冊以上の本を一度に探索できる可視化が必要だった
  • 対象データには、タイトル、著者、国、出版社、発行時期、所蔵図書館数、デジタルでの利用可否などが含まれる
  • インタラクティブ可視化は、データセット選択、個別書籍検索、発行年フィルタリング、カスタムシェーダーによる複合可視化をサポートする
  • 最大まで拡大すると、各本が本棚に差し込まれているように見える表現へ切り替わる

ISBNの構造

  • ISBN13は、ほぼすべての出版書籍に付与される13桁の番号である
  • 現在のISBN13の先頭3桁は978-または979-で固定されており、最後の1桁はチェックサムである
  • したがって、実際のISBN13空間は約20億スロットとみなせる
  • 978-と979-の接頭辞は、ISBN13がEuropean Article Numberの部分集合であることから生じた構造であり、この固定接頭辞はBooklandと呼ばれる
  • 大きなISBNブロックはInternational ISBN Agencyが国際組織に割り当て、各国は自国のブロックを出版社単位でさらに分割する
  • ISBNブロックは常に**接頭辞(prefix)**単位で割り当てられる
    • 978-4は日本に割り当てられている
    • 日本は978-4-312をある出版社に割り当てる
    • その出版社は000000-99999範囲の項目を割り当てて、978-4-312-99999-XのようなISBNを作れる
  • 国の接頭辞が長いほど、その中で割り当て可能な書籍数は減る
    • 日本は1億件のISBN空間を持つ
    • シンガポールは978-9971-接頭辞で始まり、10万件のISBNしか使えない

1次元ISBNを2次元に展開する方法

  • 978-/979-接頭辞とチェックサムを取り除くと、ISBNは0から20億の間の10進数1次元値になる
  • 最も単純な方法はピクセルを上から行単位で埋めることだが、小さな領域が横長に引き伸ばされ、ISBN構造を見づらくしてしまう
  • Hilbert curveは小領域をより正方形に近づけるが、データに存在しない空間的構造アーティファクトが生じることがある
  • この可視化ではデータにない構造を避けるため、ISBNの10進数的性質を利用したBookshelf-Curveを使う

Bookshelf-Curve

  • Bookshelf-Curveは、最初の10進桁の0-9を横に並べ、次の桁の0-9を上下方向に並べる方式を再帰的に繰り返す
  • 2階層の長方形比率を保つには、各ブロックの縦横比は√10、つまり約3.16:1になる
  • この構造はA4用紙の再帰的な縦横比の考え方に似ているが、2分割する代わりに10区間へ分ける
  • 座標変換は、ISBNの各桁を1つおきに座標へ使う方式なので単純である
  • 実装コードは一般化の試みのため50行になったが、特定のISBNの位置を手で追って見つけられるほど原理は理解しやすい

地図タイルとデータ符号化

  • 各ISBN接頭辞に対してタイル画像を生成する
  • タイルの目標サイズは約100kBで、その結果タイルサイズは2000 × 633ピクセルになった
  • データセットごとに、ピクセルへ保存する情報は異なる
    • 発行年データセットは1800を引いた値を8ビット範囲に保存する
    • 赤チャンネルはそのピクセル内書籍の平均発行年を持つ
    • 青チャンネルは存在する書籍の比率を持つ
    • たとえば50%の本が存在するなら、青チャンネル値は127/255になる
  • 最大ズームレベルでは精度のため1冊の本を1ピクセルに対応させる

GLSLシェーダーによるレンダリング

  • 当初はRGBデータをタイルに直接保存していたが、柔軟性を高めるため、より抽象的なデータを保存し、実際のレンダリングはGPUのGLSL fragment shaderで行うようにした
  • この方式により、カラーパレットを後から選んだり、任意の変換やフィルターを即時適用したり、複数データセットをその場で組み合わせたりできる
  • 発行年データは1800-2055範囲を保存するが、データの95%は1985-2024範囲にあるため、シェーダー内でこの区間に圧縮して表現できる
  • heatmapColor(float)関数は0-1値をユーザー選択のカラースケールへ変換する
  • $dataset_x構文はGLSL自体の構文ではなく、シェーダーが実際に読む画像だけを読み込むための単純な正規表現ベースのテンプレート構文である
  • 可視化の**⚙️ Advanced**オプションではシェーダーを直接編集でき、変更結果はリアルタイムで反映される
  • 各データセットの各ピクセルの意味はREADMEに整理されている

拡大時に本棚のように見せる表現

  • 完全に拡大したビューでは、各ピクセルに本のように見えるスタイルを与える
  • 各本にはランダムな幅、高さ、パターンが付くよう処理される
  • 実際の本の形と正確に一致するわけではないが、最大ズーム時の画面をより生きた情景に見せる
  • このスタイリングはすべてシェーダーで実装されている
  • GLSLとJavaScriptで同じ乱数生成結果が必要だったため、本の高さを計算してテキスト境界を合わせる部分が難しかった
  • 現在のズーム値をuniformとして渡し、2つのズームレベルの間でフェードインさせることで、本棚スタイルを滑らかに表示できる

テキスト、ツリー構造、性能

  • 画像タイルと同様に、テキストもズームレベルとビューフラスタムカリングに応じて階層構造でレンダリングする
  • 実装にはreact-threejs-fiberを使っている
  • Reactはビューが移動するとシーン要素を再帰的に追加し、各接頭辞ごとにPlane、HTMLテキスト、子接頭辞ノードを構成する
  • 多量のテキストを描画する中で、当初は性能問題が大きかった
  • HTMLをSVGの<foreignObject />内に入れ、それをcanvasへdrawImageでレンダリングしてからテクスチャとして読み込む方式が最善のアプローチだった
  • この方式は動作したものの、レンダリング過程で同期的に毎回20msの遅延を生んでいた
  • SVGをWebWorkerで描けないため、WebWorkerへ移すのは難しかった
  • 実際の性能問題は、HTML要素数を減らし、フレームごとに追加されるDOMコンテンツを制限し、とくにtext-shadow CSSフィルタースタックを削除することで大半が改善した

バーコードと出版社範囲

  • 最大拡大時には各本にバーコードが表示される
  • バーコードは、本がISBN順に並んでいるという概念を強めるために追加された
  • バーコード描画ライブラリの代わりに、13桁の数字をバーコードとして描画し、チェックディジットまで計算するLibre Barcode TTFフォントを使っている
  • OSのテキストレンダリング最適化のおかげで、この方式は扱いやすく性能も良かった
  • 各グループは通常、国単位の大きな範囲を持ち、出版社はその中のより小さな範囲を持つ
  • グループと出版社にはそれぞれ固有のランダム色が割り当てられる
  • 1つの出版社が複数範囲を持つ場合でも同じ色を使う
  • すべての範囲を同時に強調するため、出版社ごとに固有IDを付与し、それをRGBコンポーネントとして保存する
  • 出版社色にはまだ満足できない点が残っている
    • 出版社色がヒートマップのカラースケールと衝突する
    • 国の範囲が見づらい

検索移動と飛行経路

  • 本を検索したりミニマップをクリックしたりすると、その位置へフライト移動する
  • 見栄えの良い飛行経路の計算は思ったより難しかった
  • 放物線フィッティングでは結果が平凡で、その後、別の変換空間を使うアプローチを試した
  • 最終結果は完璧ではなく、約500行のコードでやや過剰設計気味だが、元のアプローチよりうまく動作する

アーキテクチャと処理パイプライン

  • バックエンドは不要
    • 画像タイルはPNGとして保存する
    • データツリーはJSONとして保存する
    • HTML、JS、CSS、PNG、JSONをGitHub Pagesのような静的ファイルホストへ置けばよい
  • フロントエンドはThreeJS、React、MobXを使う
  • この組み合わせは、再利用可能なコンポーネントで反応的かつ宣言的なGPU加速2D/3Dシーンを作るのに便利だった
  • 処理スクリプトの大半はJSで書かれており、JSONとPNGを直接出力する
  • 一部スクリプトは250GBのソースファイルを読み、SQLiteへ出力する必要があったためRustで書かれている

結果とコード

  • 結果として、ISBNが付与された出版書籍を柔軟に可視化する方法になった
  • このプロジェクトは、識別子空間がかろうじて十分なほど小さく設計されているISBNだからこそ可能だった
  • UUIDで同じことをしていたら、その大半は巨大な空白空間になっていただろう
  • ソースコードはisbn-visualizationで公開されている

関連記事

1件のコメント

 
GN⁺ 2025-02-02
Hacker Newsのコメント

  • Amazonを始めたとき、まさにこういうことをやりたかった。ただしISBNではなく、Library of Congressの3重分類を使おうとしていた
    結局、データ提供元であるBaker & TaylorとBooks In Printが3重分類を1つの文字列に潰してしまっていて、境界を安定して見つけられず、本格的に始める前に諦めざるを得なかった
    1994〜1995年版のWebでこうした「飛行」型の探索を実装するのも、間違いなく簡単ではなかったはずで、素晴らしい仕事だ

    • ここで言うLoCの3重分類が何なのか気になる
      LoC ClassificationとLoC Subject Headingsはかなり調べたが、どちらも有用な機械可読形式で自由に提供されているわけではなく、残念だった。PDFならある程度の回避策は取れる
      特にClassificationの州法セクションは、州ごとの分類密度が非常に不均一だった。記憶ではNYとCAが圧倒的に複雑で、PAが少し離れた3位、多くの「フライオーバー」州はほとんど笑えるほど単純で互いに似ていた。これは各州の成文法、規制、判例法の複雑さを反映しているように思える
      もう一つ興味深い歴史的事実として、分類体系とアルファベット式の最上位区分は、LoCの起源となったThomas Jeffersonの個人蔵書から直接来ているように見える
      関心があれば、Hathi TrustにあるLibrarian of Congressの議会提出年次報告書で、Classificationの発展と拡張の歴史を多く見ることができる
      Classification: <https://www.loc.gov/catdir/cpso/lcco/>
      Subject headings: <https://id.loc.gov/authorities/subjects.html>
      Annual reports — Recent: <https://www.loc.gov/about/reports-and-budgets/annual-reports...> / Historical archive to ~1866: <https://catalog.hathitrust.org/Record/000072049>
    • 以前Baker & Taylorとやり取りした立場からすると、まったく驚かない
      取引した会社の中でも技術的に最も遅れていたところの一つで、2020年初めにアカウントを閉じるまで、発注書と精算を紙、PDF、メールで処理していた。一時は書類をFAXで送らせていたこともあったと思う

  • ISBNが別々の本に重複して割り当てられることは珍しくないので[0]、「ISBN空間のすべての本」という表現は誇張かもしれない
    また、チェック数字が残りのISBNと合わない不正なISBNを持つ本もある。チェック数字を直すと別の本と一致してしまう場合、その本はブログ記事が仮定しているISBN空間の外に置かれることになる
    [0] https://scis.edublogs.org/2017/09/28/the-dreaded-case-of-dup...

    • そもそも割り当てられていなかった可能性もある
      チェコの出版社の既知の最小ISBNを見ていたら別の色が飛び出してきたが、https://books.google.cz/books?vid=ISBN9788000000015&redir_es...は正しいISBNではなさそう :-) ただし、その本にそんな露骨な偽ISBNが入っているのか、それともGoogle Booksのデータエラーなのかは分からない

  • 印象的なプレゼンテーションだ
    ただしこの画面はISBNカタログ全体ではなく、Anna's Archiveの所蔵内容だけを反映している。Annaの収集バイアスのため、特定の言語範囲に偏ったバイアスが見え、黒で表示された領域はアーカイブにない項目だ

    • 完全に正確ではない。Anna's Archiveには、実際のファイルとして持っている本のデータベースと、メタデータだけを知っている本のデータベースが別々にある
      メタデータのデータベースは複数の出典から来ており、私の知る限りかなり完全に近い。黒い部分はほとんどが、割り当てられた本のない領域である可能性が高い

  • 本当に素晴らしく、驚くべき情熱プロジェクトであり、優れた資料だ
    拡大するとタイトルとバーコードが見え、マウスを乗せると表紙と詳細情報まで出てくる。望めるものはほとんど揃っている
    改善案としては、左上の浮いている白いパネルと右上の要素を隠すチェックボックスがあるとよさそうだ。こうした可視化に「没入」するのが好きなのだが、浮いている要素がその体験から少し引き戻してしまい、楽しさと機能性が少し下がっている

  • これは、Microsoftが中止する前に神経画像分野で使われていた優れたWebインターフェース、Microsoft Silverlight PivotViewerにぴったりの事例だ
    Gary W. Flakeが使い方を見せる印象的なTED講演がある
    https://m.youtube.com/watch?v=LT_x9s67yWA
    2011年に書いたIEEE論文もある。これがWeb標準ではないのが本当に残念だ
    https://www.dropbox.com/scl/fi/bl8zkjs3y47q3377hh3ya/Yan_Wil...

  • とても素晴らしい可視化だ
    ここにさらに素晴らしい投稿作品がある: https://software.annas-archive.li/AnnaArchivist/annas-archiv...
    私の作品はhttps://isbnviz.pages.devにある

  • 拡大すると本棚のように見える。本当にすばらしい

    • 改善の余地：文庫版と製本版が並んで表示されるが、同じに見える。電子書籍はよく分からない

  • すばらしい。現実版のLibrary of Babelみたいだ： https://libraryofbabel.info/
    さまざまなVRのたわごとの中でも、現実の無限図書館や無限博物館なら、お金を払ってもいいかもしれない

    • 残念ながら、この特定の実装では作家たちがそのお金をまったく受け取れないだろう
      合法的に提供されているダウンロード可能なすべてのテキストにアクセスできるようにするプロジェクトだったなら、ずっと興味深かったと思う。たとえば、こういう場所のインターフェースのように：
      https://onlinebooks.library.upenn.edu/

  • 現在の形式のプレゼンテーションは、少し圧倒される感じがした
    左上のプリセット部分が、実際にはAAへの収録有無、希少度、Google Booksへの収録有無といった追加のデータ可視化軸につながっているのだと理解するまで、少し時間がかかった。それでも、可視化とデータの深さは豊かだ
    地域クラスターの様子を示す https://archive.anarchy.cool/blog/all-isbns.html#visualizing もよかった
    年別プリセットは、それ自体でも地域別の出版活動の活発さを見るうえで興味深かった。Polandは最近非常に活発で、Norwayは比較的静かに見える。Chinaは2005年ごろから増え、ここ10年で非常に大きくなったようだ
    United Statesにも奇妙な点がある。聞いたことはないが、Blackstone Audio、Blurb Inc.、Draft2Digitalが膨大な数のISBNを出している

    • かなりノイズが多いのは確かで、高いデータ密度に焦点を当てているため、ある程度は意図された部分でもある
      もう少しミニマルな表示（色を減らし、同時にテキストレベルを1つだけ表示）はここにある：
      https://phiresky.github.io/isbn-visualization/?dataset=all&g...
      一部のテキスト、たとえばN publishersの部分を隠したり、マウスオーバー情報を減らしたりする形で、さらに調整できそうだ

  • 飛行経路は双曲上半平面上の運動としてモデル化すると、かなり合理的に考えられる。xを端点間の線形経路上の位置、yをビューポートの一辺の長さとすればよい
    互いに一致する2つの計量を考えた。まず、階層的なタイル地図を仮定し、読み込まれるタイル数を最小化する方式だ。yをビューポートの一辺の長さとして使うと、xだけ水平移動するコストはx/yタイルで、y_0からy_1へ拡大・縮小するとabs(log_2(y_1/y_0))タイルを読み込むので、ds = dy/yと一致する。合わせるとds^2 = (dx^2 + dy^2)/y^2で、ちょうど上半平面の計量になる
    別の見方としては、ビューポートの「オプティカルフロー」を何らかの意味で最小化しているとも見られる。これもスケールが違うだけで同じ計量になる。拡大せずにxだけパンすると、すべてがx/yだけ、つまりビューポートに対する比率だけ移動する。k倍に拡大すると、(u,v)のピクセルは(ku,kv)へ行き、変位は(u,v)(k-1)になる。一辺の長さがyからy+dyになると(u,v)dy/yになるので、変位をどう平均するかによって、dy/yの何らかの定数倍になる
    すると望ましい測地線はy=0に中心を持つ円であるホロサイクルだが、曲線に沿った動きを計算するには少し作業が必要になる。θ_0からθ_1まで弧を取ると、全体の時間はdtheta/y = dθ/sin(θ)を積分して得られるため、正確にやるにはt = ln(csc(θ)-cot(θ))を反転する必要がある。近似したほうがよさそうだと思ったが、Mathematicaがθ = atan2(1-2    e^(2t), 2    e^t)になると教えてくれたので、それほど悪くはない
    「blub space」のロジックと比べると、そこの有効計量はds^2 = dz^2 + (z+1)^2 dx^2のようだ。z=1/yをズームレベルとする極座標で、dz=dy/y^2を使うとds^2 = dy^2/y^4 + dx^2*(1/y^2 + ...)になる。つまり既存の実装は、双曲モデルよりも高い拡大レベルでパンにずっと多くの時間を費やしているように見える。4倍から2倍に下げるコストが、2倍から1倍に下げるコストの2倍なのに、視覚的には同じだからだ

    • 実際に触ってみると予想とはかなり違い、はるかに大きくズームアウトした。拡大コードの一部を見落としていたためだ
      彼らのzoomはスケール係数ではなく、私の「y」に相当するので、計量はds^2 = dy^2 + (C-y)^2 dx^2になる。ここでCは最大ズームレベルより少し大きい。その曲線がさらに遠くまでズームアウトしようとする場合のための特殊処理もある
      完全にズームアウトした状態（zoom=1）で端までパンするコストが同じになるよう正規化すると、非常に深く拡大した状態ではパンのコストがほぼ平坦で、相対的に浅い拡大状態では双曲モデルよりコストが大きい。だから短い距離ではビューポートが非常に速く動くように感じられ、長い距離ではほぼ最後までズームアウトするように見えることに寄与しているようだ。中間の拡大レベルが不利なので、ほぼ最後まで行くほうがよくなる