タグ

アルゴリズムに関するnabehiroのブックマーク (8)

  • ID生成大全 - Qiita

    セッションIDやアクセストークン、はたまた業務上で使う一意の識別子など、いろんなところで一意のIDを生成しなきゃいけないケースが存在します。 そこで世間で使われているIDの生成方法について調べてみました。 選択基準 ID生成における要求として、以下の観点が上げられるかと思います。 生成の速度 大量にデータを短期間で処理し、それらにIDを付与する場合、ID生成そのものがボトルネックとなることがあります。 推測困難性 IDを機密情報と結びつける場合、IDを改ざんされても、機密データが見れないようにできている必要があります。 順序性 採番した順にデータをソートする必要がある場合は、IDがソートキーとして使えないといけません。 それぞれについて各生成手段を評価します。 ID生成の手段 データベースの採番テーブル 採番用のテーブルを作り、そこで番号をUPDATEしながら取得していくやりかたです。古い

    ID生成大全 - Qiita
  • 近似文字列アルゴリズムのgestalt pattern machingについてメモ

    Google 検索でタイポをすると、意図したであろう綴りを教えてくれたり、意図通りの検索結果を返してくれる。 このスペルチェック機能では、入力文字列が来の文字列とどのくらい似ているのかを評価するアルゴリズムが肝で、編集距離のアルゴリズムはよくしられている。 ふとしたことから、Ratcliff/Obershelp pattern recognition(gestalt pattern maching ともいう) という編集距離とは別のアルゴリズムに出くわした。 このアルゴリズムは1980年代から存在するが、より利便性の良いアルゴリズムが発明されていったからなのか、wikipedia に載っていないくて、手元のアルゴリズムにもみあたらない。 まだこのアルゴリズムが輝いていた 1988 年に、 Dr. Dobb’s Journal に発表された次の記事(サンプル実装はアセンブリ言語!)を元に

    近似文字列アルゴリズムのgestalt pattern machingについてメモ
  • 初心者でもアルゴリズムの学習ができる入門本とサイト一覧 -

    Photo by VFS Digital Design 皆さんはアルゴリズムやデータ構造について知っているでしょうか。情報系の学部出身の人は学校の授業でやったかもしれません。一方で学校で情報系の勉強をせずにITエンジニアになったという方は、アルゴリズムやデータ構造について一度は「勉強したほうが良いんだろうな」と思いつつも、実際の業務であんまり必要なさそうだし、難しそうだし、DevOpsやオブジェクト指向やフレームワークについて学ぶので手一杯で未着手、という人も多いのではないでしょうか。 今回はそんな方に向けて、アルゴリズム、データ構造を学ぶ意義と、それらを学ぶときに役立つとサイトについてまとめました。 ■アルゴリズム、データ構造を学ぶ意味 アルゴリズムやデータ構造について語られるときに、非常に良く言われる事として「そんなものは実務に役立たたないので必要ない」という意見があります。当にア

    初心者でもアルゴリズムの学習ができる入門本とサイト一覧 -
  • 類似画像検索システムを作ろう - 人工知能に関する断創録

    C++版のOpenCVを使ってカラーヒストグラムを用いた類似画像検索を実験してみました。バッチ処理などのスクリプトはPythonを使ってますが、PerlでもRubyでも似たような感じでできます。 指定した画像と類似した画像を検索するシステムは類似画像検索システムと言います。GoogleYahoo!のイメージ検索は、クエリにキーワードを入れてキーワードに関連した画像を検索しますが、類似画像検索ではクエリに画像を与えるのが特徴的です。この分野は、Content-Based Image Retrieval (CBIR)と呼ばれており、最新のサーベイ論文(Datta,2008)を読むと1990年代前半とけっこう昔から研究されてます。 最新の手法では、色、形状、テクスチャ、特徴点などさまざまな特徴量を用いて類似度を判定するそうですが、今回は、もっとも簡単な「色」を用いた類似画像検索を実験してみます

    類似画像検索システムを作ろう - 人工知能に関する断創録
  • Aho Corasick 法 - naoyaのはてなダイアリー

    適当な単語群を含む辞書があったとします。「京都の高倉二条に美味しいつけ麺のお店がある」*1という文章が入力として与えられたとき、この文章中に含まれる辞書中のキーワードを抽出したい、ということがあります。例えば辞書に「京都」「高倉二条」「つけ麺」「店」という単語が含まれていた場合には、これらの単語(と出現位置)が入力に対しての出力になります。 この類の処理は、任意の開始位置から部分一致する辞書中のキーワードをすべて取り出す処理、ということで「共通接頭辞検索 (Common Prefix Search)」などと呼ばれるそうです。形態素解析Wikipediaはてなキーワードのキーワードリンク処理などが代表的な応用例です。 Aho Corasick 法 任意のテキストから辞書に含まれるキーワードをすべて抽出するという処理の実現方法は色々とあります。Aho Corasick 法はその方法のひと

    Aho Corasick 法 - naoyaのはてなダイアリー
  • Double-Array

    ダブル配列( Double-Array )は, トライ( Trie )のデータ構造の一種であり, 小さい辞書で高速に検索できるという特長を持っています. 実際に,茶筌( ChaSen )や 和布蕪( MeCab )などの 形態素解析器で利用されているという実績があります. ダブル配列では,配列を使ってトライを表現します. 配列の各要素が BASE, CHECK という二つの整数を持つので,頭文字をとって配列 BC と呼ぶことにします. 以降の説明では,配列 BC の要素 x の BASE, CHECK を それぞれ BC[x].BASE, BC[x].CHECK と記述します. 通常,BASE, CHECK は個別の配列として紹介されますが, 特に分割して考える必要がないので,このような説明にしました. 基的に,配列 BC の各要素は トライの節と一対一で対応します. そのため,対応する

  • Trie TreeならびにDouble Array Trie Treeを用いたパフォーマンスの検証

    This document summarizes key points from chapters 11 and 15 of Programming Hive. It discusses choosing compression codecs for intermediate and final outputs in Hive, how different compression schemes like LZO, Snappy, and BWT work, and enabling compression in Hive. It also covers Hive file formats like SequenceFiles, RCFiles, and ORCFiles. RCFiles store data columnarly and use RLE compression. ORC

    Trie TreeならびにDouble Array Trie Treeを用いたパフォーマンスの検証
  • 知ってる? クレジットカード番号の意味と暗算認証術

    知ってる? クレジットカード番号の意味と暗算認証術2011.01.24 12:0030,766 satomi 暗算で偽造カード見分けられるなんて...知らなかった! 毎日のように使うクレジットカード。丸暗記して時間セーブしてる人も、あの数字16桁の意味までは知らないんじゃ? 16個の数字にはそれぞれ意味があるんですよ。米国で人気のオンライン資産管理サービス「Mint」がズバリ図解してくれました! (図の訳) 1)最初の1桁:主要産業識別子 (MII:Major industry identifier)。カード発行者の業界を表します。 0 予備 1、2 航空 3 旅行・娯楽 4、5 銀行・金融 6 商品輸送・銀行 7 石油 8 通信 9 国ごとの割り当て分 2)MIIを含む最初6桁:発行者識別番号(IIN:Issuer Identifier Number)。カード発行者の身元を表します。 [

  • 1