ID生成大全 - Qiita
セッションIDやアクセストークン、はたまた業務上で使う一意の識別子など、いろんなところで一意のIDを生成しなきゃいけないケースが存在します。 そこで世間で使われているIDの生成方法について調べてみました。 選択基準 ID生成における要求として、以下の観点が上げられるかと思います。 生成の速度 大量にデータを短期間で処理し、それらにIDを付与する場合、ID生成そのものがボトルネックとなることがあります。 推測困難性 IDを機密情報と結びつける場合、IDを改ざんされても、機密データが見れないようにできている必要があります。 順序性 採番した順にデータをソートする必要がある場合は、IDがソートキーとして使えないといけません。 それぞれについて各生成手段を評価します。 ID生成の手段 データベースの採番テーブル 採番用のテーブルを作り、そこで番号をUPDATEしながら取得していくやりかたです。古い
近似文字列アルゴリズムのgestalt pattern machingについてメモ
Google 検索でタイポをすると、意図したであろう綴りを教えてくれたり、意図通りの検索結果を返してくれる。 このスペルチェック機能では、入力文字列が本来の文字列とどのくらい似ているのかを評価するアルゴリズムが肝で、編集距離のアルゴリズムはよくしられている。 ふとしたことから、Ratcliff/Obershelp pattern recognition(gestalt pattern maching ともいう) という編集距離とは別のアルゴリズムに出くわした。 このアルゴリズムは1980年代から存在するが、より利便性の良いアルゴリズムが発明されていったからなのか、wikipedia に載っていないくて、手元のアルゴリズム本にもみあたらない。 まだこのアルゴリズムが輝いていた 1988 年に、 Dr. Dobb’s Journal に発表された次の記事(サンプル実装はアセンブリ言語!)を元に
初心者でもアルゴリズムの学習ができる入門本とサイト一覧 - paiza times
Photo by VFS Digital Design 皆さんはアルゴリズムやデータ構造について知っているでしょうか。情報系の学部出身の人は学校の授業でやったかもしれません。一方で学校で情報系の勉強をせずにITエンジニアになったという方は、アルゴリズムやデータ構造について一度は「勉強したほうが良いんだろうな」と思いつつも、実際の業務であんまり必要なさそうだし、難しそうだし、DevOpsやオブジェクト指向やフレームワークについて学ぶので手一杯で未着手、という人も多いのではないでしょうか。 今回はそんな方に向けて、アルゴリズム、データ構造を学ぶ意義と、それらを学ぶときに役立つ本とサイトについてまとめました。 ■アルゴリズム、データ構造を学ぶ意味 アルゴリズムやデータ構造について語られるときに、非常に良く言われる事として「そんなものは実務に役立たたないので必要ない」という意見があります。本当にア
類似画像検索システムを作ろう - 人工知能に関する断創録
C++版のOpenCVを使ってカラーヒストグラムを用いた類似画像検索を実験してみました。バッチ処理などのスクリプトはPythonを使ってますが、PerlでもRubyでも似たような感じでできます。 指定した画像と類似した画像を検索するシステムは類似画像検索システムと言います。GoogleやYahoo!のイメージ検索は、クエリにキーワードを入れてキーワードに関連した画像を検索しますが、類似画像検索ではクエリに画像を与えるのが特徴的です。この分野は、Content-Based Image Retrieval (CBIR)と呼ばれており、最新のサーベイ論文（Datta,2008）を読むと1990年代前半とけっこう昔から研究されてます。 最新の手法では、色、形状、テクスチャ、特徴点などさまざまな特徴量を用いて類似度を判定するそうですが、今回は、もっとも簡単な「色」を用いた類似画像検索を実験してみます
Aho Corasick 法 - naoyaのはてなダイアリー
適当な単語群を含む辞書があったとします。「京都の高倉二条に美味しいつけ麺のお店がある」*1という文章が入力として与えられたとき、この文章中に含まれる辞書中のキーワードを抽出したい、ということがあります。例えば辞書に「京都」「高倉二条」「つけ麺」「店」という単語が含まれていた場合には、これらの単語(と出現位置)が入力に対しての出力になります。 この類の処理は、任意の開始位置から部分一致する辞書中のキーワードをすべて取り出す処理、ということで「共通接頭辞検索 (Common Prefix Search)」などと呼ばれるそうです。形態素解析、Wikipedia やはてなキーワードのキーワードリンク処理などが代表的な応用例です。 Aho Corasick 法 任意のテキストから辞書に含まれるキーワードをすべて抽出するという処理の実現方法は色々とあります。Aho Corasick 法はその方法のひと
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を用いたパフォーマンスの検証
2. 1 はじめに ブログなどの大量のテキストデータが蓄積される CGM サイトでは、必然的にシステムや プログラムの中でも文字列処理の回数が多くなる。そのため効率的なアルゴリズムの採用 は、サイトのプログラム処理速度、ひいては対ユーザのページレスポンスタイムに関わる 重要な事案となる。 今回は、文字列の全文一致検索や前方一致検索処理において効率的なアルゴリズムとして 知られる「トライ木」についてそのパフォーマンスの検証を行った。 2 TrieTree について 2.1 アルゴリズムの内容 以下、トライ木についての解説を wikipedia より引用する。 トライ木（Trie）とは、順序付き木構造 (データ構造)の一種。プレフィックス木 （Prefix Tree）とも呼ばれる。キーが文字列である連想配列の実装構造として使 われる。2 分探索木と異なり、各ノードに個々のキーが格納されるのでは
知ってる？ クレジットカード番号の意味と暗算認証術
知ってる？ クレジットカード番号の意味と暗算認証術2011.01.24 12:0029,477 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
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
