StringBeginners

https://sites.google.com/view/stringbeginners/workshop

StringBeginners という文字列データ構造とアルゴリズムを学ぶワークショップがある。ほとんどの内容についてスライドが残されており、後から読んでも興味深いものが多い。

StringBeginners で扱われた内容を、StringBeginners 公式サイトからプログラムを引用し、リンク集として残しておく。

注意: 筆者はこの研究会の関係者ではありません。

2018-11-02

• ハルヒ問題（最小超置換）
• String cadences
• SA-IS
• General Pigeonhole Principle

2018-12-07

• Order Preserving Pattern Matching
• string attractorsの簡単な紹介
• 厳密文字列照合アルゴリズム今昔(仮) by 喜田
• 配列のローテーションを線形時間でin-placeに実行せよ by @kgoto

2019-02-07

• RLBWT線形時間復元アルゴリズム
• 構造データ学習の観点から見たカーネル法入門
• GLOUDS
• Minimal Unique Substring

2019-03-22

• SA-IS, SACA-Kの解説
• トライとダブル配列の基礎

2019-04-26

• オンライン索引構造四方山話
• 連定理
• 離散構造処理系入門

2019-06-24

• 頻度を数える ～ただしボードは小さいものとする
• Level Ancestor （でPath decompositionが学べたらいいなあ）
• 篠原：BWTの世界を上空から眺めたい
• kgoto: グラフの省領域探索

2019-08-06

• 神田：Fast Succinct Trie
• 西本：Optimal Construction of Compressed Indexes for Highly Repetitive Texts
• 坂内：パラメータ化接尾辞/LCP配列

2019-09-20

• 中島：○○○don words
• 藤重：接尾辞データ構造の眺め方
• @kgoto: 文字列の性質の眺め方
• Shawna：回文について，少し考えてみる

2019-11-12

• 佐々木：SATフィルター
• 木村：Random Features
• 松本：Numbered Automatonによる文字列の完全ハッシュ

2019-11-30/2019-12-01

• tkida: ビットパラレルの極意(pdf, pptx)

• 高木: 1の位置（Least Significant Set Bit & Most Significant Set Bit の定数時間計算）

• @tkbtkysms: ビット列のrank辞書

• @kampersanda: EliasFano符号

• 中島: ポリオミノの凸判定問題を Lyndon 文字列で解く

• @kgoto: 赤黒木の本質

• @triplefields: Σ上の文字列を簡潔に表現する

• 鶴田: Dynamic Z-Fast Tries

• @m_funa0000: String Cadences Revisited

2020-01-31

• Shawna: 二次元文字列照合
• @kgoto: 機械学習入門
• @tkbtkysms: SIMDについて調べてみた

2020-05-29

• 木村：新型Cウイルスから学ぶ精度指標とベイズ統計入門
• 坂内：Incompressibility methodを使ったソートアルゴリズムの平均計算量解析

2020-07-17

• 笹川：クエリとテキストのプライバシを考慮したマルチパーティ正規表現照合プロトコル
• Dominik：In-Place (Bijective) BWT の構築

2020-08-21

• 西本：Bidirectional Scheme
• @kgoto：ソリティアソートの紹介

2021-02-10

• @kgoto：強暗黙静的指探索 Strong Implicit Static Finger Search
• @kampersanda：動的類似検索

2021-06-11

• @kampersanda：モダンプロセッサでの二分探索
• @kgoto：LCP配列の構築アルゴリズムたち