転置インデックスの圧縮技法
転置インデックスは、検索エンジンの実装において、中心的な役割を果たすデータ構造である。 転置インデックスのデータ構造とアルゴリズムは、クエリ処理アルゴリズムとともに、検索エンジンの性能に直結する。とくに大規模な検索エンジンにおいては、キャッシュ効率を高めてクエリ処理を高速化するために、転置インデックスの圧縮は必要不可欠となっている。 この記事では、転置インデックス、とくにポスティングリストの圧縮について、近年の手法を簡単にまとめる。 目次 転置インデックスの基本 転置インデックスのデータ構造と特性 転置インデックスのアクセスパターン 近年のインデックス圧縮技法 Variable-Byte Family VByte Varint-GB Varint-G8IU Masked-VByte Stream-VByte Opt-VByte Simple Family Simple9 Simple16
最短経路問題総特集！！！～BFSから拡張ダイクストラまで～ - Qiita
Deleted articles cannot be recovered. Draft of this article would be also deleted. Are you sure you want to delete this article? 基本的アルゴリズム（幅優先探索など）から応用（経路復元、拡張ダイクストラなど）まで、最短経路問題に関するアルゴリズムを総特集しました。 基本的なグラフ理論の用語については、次を参考にしてください。 グラフ理論 用語集 queueなどのデータ構造の用語については、次のスライドの後半を参考にしてください。 C++ STL講習会 by @e869120 最短経路問題とは 一般的に、次のような問題とされます。 $V$ 頂点と $E$ 辺からなるグラフが与えられる。頂点 $u$ と 頂点 $v$ を結ぶパスのうち、重みの総和が最も小さいものはどれ
IDA* -- Iterative Deepening A* - Qiita
自分は孫弟子にあたるらしいRichard E. Korf 先生の論文紹介です。 会ったことないですがKorf先生→ https://www.youtube.com/watch?v=EnX8cQPiB1M https://www.youtube.com/watch?v=TAjyI06Q1x8 IDAはAと同じく最適解を返すアルゴリズムですが、A*と異なり メモリ使用量が線形 であるという違いがあります。 Iterative Deepening Depth First Search だれだ反復深化深さ優先探索なんて長ったらしい名前を付けたのは。 反復Xは長いのでIDDFSと呼びましょう。 IDDFSは、ダイクストラの深さ優先版です。 ダイクストラやA*などの最良優先探索系、もとい幅優先探索系に共通する問題は、OPENリストを全部メモリに確保しておかないといけないという点です。 しかし、実際のコ
chokudaiサーチのメモ - メモ
CODEVS 5で話題になったchokudaiサーチのリンク集 正式名は beam stack search だとか [追記２] ちょうだいさん本人のブログで解説されるのでそっちを読みましょう！ chokudai.hatenablog.com [追記] 診断人さん(@nico_shindannin)の調査によると、２つはアルゴリズムも目的も違うものであるとの指摘 shindannin.hatenadiary.com Beam stack search - Wikipedia] Chokudai search from AtCoder Inc. www.slideshare.net 説明 chokudaiサーチって何やねんって説明をある程度アルゴリズム解ってる人向けにすると、 ・幅1のビームサーチをする。この時、全部の過程と評価を残す ・残した評価から初手に戻り、幅2のビームサーチっぽいのに
Interpolation Search - Negative/Positive Thinking
Interpolation Searchとは 補間探索、内挿探索 二分探索での範囲の中間値を利用する代わりに、範囲の両端の値から探したい値の位置にあたりをつけて、その値を利用して探索していく方法 二分探索では、配列の値に関係なく範囲の中間の値を利用して探索 探索時間はO(log log n) 二分探索では、O(log n) データに依っては、二分探索の方が速くなる場合もあり得る 計算例 配列vが「1,2,3,5,6,10,12」として、 left = 0, v[left] = 1 right = 6, v[right] = 12 である時、 2分探索では、mid = floor( (left + right) / 2 ) = floor( (0+6) / 2 ) = 3のように決めたりするが、 Interpolation Searchでは、値も考慮し、value=6を探したい場合、 mid
詰将棋を解く時の脳の使い方 - 将棋棋士 遠山雄亮のファニースペース
先日、若島正著「盤上のファンタジア」という詰将棋作品集を解いていると書いたところ、業界内で意外と反響がありました。 詰将棋が解ける時 その作品集の中の問題で、合計10時間以上苦しんだものがありました。 問題の途中図に以下のような部分図が発生します（ネタバレを防ぐため、一部の駒は除いています）。 ここで▲７二銀打と攻めると、非常に際どいのですがどうしても詰みません。 この図に至るまでの手順もとても複雑。そして総計で10時間以上経ったある時、▲８二銀と打つ手を発見しました。 ６一の銀も取られますし、不利感のある手です。 ですがこの手が妙手で、以下は守備馬の只捨てなどを経て17手程度かかって収束します。 この▲８二銀に辿り着いた時、守備馬の只捨ても含め、その後の17手が瞬く間にわかりました。 10時間以上分からなかったのに、１手（▲８二銀）が見えたことで何故一気にその後の全てが分かるのでしょう。
AlphaBeta探索で経路依存の値を判定する方法 - Qiita
なんぞ？ AlphaBeta探索では、ゲーム木を木構造とみなして探索しているけど、現実的には合流があったりするので、それを効率的に処理するため(だけではないけど)に置換表があったりして、しかしゲームによっては辿った経路によって発動したりしなかったりするルールがあったりなんかもして、色々めんどくさいわけです。 そんなわけで、AlphaBeta探索をしていて、その時の評価値が経路に依存したものなのか否かを判定したくなったりすることもあるわけですが、割と頭がこんがらかるので、実装方法をまとめてみました。 どうやるの？ ↓こんな感じ。 末端では、それが経路依存な性質を持つか否かでフラグを設定する。 αを超えた場合(βカットを含む)は、αを超えた子ノードがtrueなときだけtrueにする。 αを超えなかった場合は、子ノードがどれか一つでもtrueならtrueにする。 β以上の子ノードがあった場合、そ
実践QBVH
2014年6月に開催されたSSII2014（http://www.ssii.jp/）のチュートリアル講演用資料です． 使用したコード等はこちら． https://github.com/norishigefukushima/SSII2014 アブストラクト 「CPUのクロック数が年月とともに増加する時代は終わり、プログラムの高速化をCPUの性能向上に任せることのできるフリーランチの時代は終わりを迎えています。しかしムーアの法則はいまだに続いており、CPUはマルチコア化、SIMD化という形で高性能化が続いています。本チュートリアルでは、計算コストの高い画像処理を高速化するために、CPUの能力をあますことなく引き出す、マルチコアプログラミング、SIMDプログラミングを解説します。」
三分探索と黄金分割探索 - naoya_t@hatenablog
はい、毎度おなじみのグラフ描きたいだけのエントリですw 今回のお題は「三分探索（ternary search）」。 二分探索（binary search）は割とおなじみかと思うのですが、二分探索が単調増加(減少)関数fについてf(x)=kとなるxを求めるのに対し、三分探索（とか黄金分割探索）は凸関数の極値を求めるのに用います。 詳しくは http://d.hatena.ne.jp/ir5/20090630/1246349028 http://d.hatena.ne.jp/nodchip/20090303/1236058357 辺りを見て頂くとして。 三分探索 探索領域(x0,x3)を三等分するx1,x2を選びます。(x0,x1,x2,x3) で、f(x1)とf(x2)を比べ、f(x)が下に凸な関数なら値が大きい方、上に凸な関数なら値が小さい方の外側（x1ならx0-x1, x2ならx2-x3
メタヒューリスティクス - Wikipedia
この記事は検証可能な参考文献や出典が全く示されていないか、不十分です。 出典を追加して記事の信頼性向上にご協力ください。（このテンプレートの使い方） 出典検索?: "メタヒューリスティクス" – ニュース · 書籍 · スカラー · CiNii · J-STAGE · NDL · dlib.jp · ジャパンサーチ · TWL (2023年8月) メタヒューリスティクスとは、組合せ最適化問題のアルゴリズムにおいて、特定の計算問題に依存しないヒューリスティクスのことである。 近年では、上記の定義から拡張され、特定の問題に依存しない、汎用性の高いヒューリスティクス全般を指すこともある。そのため、組合せ最適化問題のアルゴリズムに限らず、連続最適化問題に対するアルゴリズムも含む解釈も存在する。 通常ある問題に対しての「解法」が存在するとき、その解法が適用できる範囲はその問題に対してのみである。 と
4段階の思考スキルレベル - Chikirinの日記
将棋ソフトに関しておもしろかったのは、先日も書いた「探索」と「局面評価」という思考プロセスです。 １）探索＝とりうる選択肢を、自分の選択肢→相手の対応策（選択肢）→自分の選択肢、と深掘りしつつリストアップ ２）局面評価＝上記の過程で現れる局面を、どの程度、自分に有利か（不利か）評価する ３）その上で、自分にとって最も有利な局面につながる選択肢を選ぶ 探索とは、下記のような図＝探索木＝ツリーのイメージです。 （『人間に勝つコンピュータ将棋の作り方』より） この探索と局面評価というステップは、ビジネスや個人生活などあらゆる意思決定の場面で使われてます。 将棋のような完全情報ゲームでないため、より複雑ですが、ビジネスでは、 ・自社が値段を下げる→他社が対抗してくる→自社はどうする？・・・であったり、 ・自社が買収を提案する→第三者が価格を釣り上げる→公正取引委員会がいちゃっもんをつける→自社はど
暗記なんかで勝てたりしません - Chikirinの日記
今日は、将棋ソフトがどのように“将棋を学んできたのか”について、まとめておきます。 今から40年ほど前の 1975年頃、人工知能研究の一環として将棋ソフトの開発は始まったそうです。 その進化の流れは、ざっくり言えばこんな感じ？ １．ルールを覚えさせる ２．金言などをプログラム化する ３．探索と駒得で手を選ばせる ４．局面評価について、機械学習をさせる １の「ルールを覚えさせる」というのは、各駒の動ける場所を教え、“二歩”など反則となるルールを教えるってことです。 でも、駒の動かし方がわかるようになっただけでは勝てたりはしません。今の私と同じです。 ちなみに「反則にならない手」は合法手と呼ばれます。 次に「金言をプログラム化する」ってことが行われたみたいです。 将棋には勝ちやすくなるための格言がたくさんあります。 「玉飛接近すべからず」「二枚替えなら歩ともせよ」みたいな言葉ですが、そういうの
力まかせ探索 - Wikipedia
力まかせ探索（ちからまかせたんさく、英: brute-force search）またはしらみつぶし探索（英: exhaustive search）は、単純だが非常に汎用的な計算機科学の問題解決法であり、全ての可能性のある解の候補を体系的に数えあげ、それぞれの解候補が問題の解となるかをチェックする方法である。 バックトラッキングと混同されやすいが、バックトラッキングでは解候補の大部分を明示的に探索することなく捨てることができる。例えば、エイト・クイーンは、8個のクイーンをチェスボード上で互いに取り合えない状態で配置するものである。力まかせ探索では 通りの配置を全て順にチェックしていく。バックトラッキングでは、2つのクイーンが互いに取り合える状態なら他のクイーンがどう配置されていても考慮に値しないという事実を使って、チェックすべき配置数を大幅に減らし、高速に解くことができる。 力まかせ探索は実
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
Patrick von Platen on Twitter: "Beam search doesn't have to be boring! Now you can bring more variety into your beam search with Diverse Beam Sear… https://t.co/hyXEQWKSJa"
[PDF]陣内佑 (2020) ヒューリスティック探索入門
piqcy on Twitter: "言語モデルで実際文を生成するときに必要なDecodingについて、各種手法とTransformernによる実装を紹介している記事。単純に一番確率が高い単語をとっていくGreedy Searchから代表的なBeam Searchなど… https://t.co/faETArJFzQ"
cakes（ケイクス）
[AAAI-16] Tiebreaking Strategies for A* Search: How to Explore the Final Frontier
IBM Developer
高速な最近某探索