衝突 (計算機科学)とは? わかりやすく解説

Weblio 辞書 > 辞書・百科事典 > 百科事典 > 衝突 (計算機科学)の意味・解説 

衝突 (計算機科学)

出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2018/10/08 03:05 UTC 版)

Jump to navigation Jump to search

計算機科学には全く限らず、ハッシュ関数のような種類の関数を使うような場面で、衝突(: collision)とは、2つの異なるデータからハッシュ関数などで生成したハッシュ値など(チェックサム・フィンガープリント・メッセージダイジェストなど)の値が同じ値(シノニム)になることである。

概要

ほとんどの分野において、衝突は一般に望ましくない結果ではある。ここでは「望ましくなさ」と呼ぶが、その「望ましくなさ」はその応用の目的によって異なる。また鳩の巣原理により、ある集合全体からその集合より小さい集合への写像では必ず衝突が発生するが、メッセージダイジェストなどではその確率が十分に低いかどうかが問題となる。

相同DNA配列や、ほぼ同じ内容の音声ファイルなど、よく似たデータを同一視するためにハッシュ関数とフィンガープリントを使用する場合、ハッシュ関数は似たデータに対して似た結果を出し、あるいは衝突を発生する(確率ができる限り大きくなる)ように設計される。これは一般と逆に必要な場合には衝突が望まれる例である。

ビットの化けや抜けや混入をチェックするチェックサムなどはよく似た入力に対して、可能であれば十分に異なるハッシュ値を生成することが望まれ、衝突を発生させる確率ができる限り小さくなるように設計される。一方で全く異なるデータ間での衝突については通常は意識されない。こういった誤り検出訂正の類はハッシュとは別とすることもある。

ハッシュテーブルにおいて、衝突はルックアップ処理のコストを増加させる。こういった応用には関数の計算量と結果の品質のどちらを重視するか等のトレードオフもある。またハッシュテーブルを実装するいくつかの技法との相性、あるいは入力に現れる値が完全にランダムか何らかの性質があるのか、といった考慮すべき要素もある。入力に現れうる値が予め全て既知なのであれば完全ハッシュ関数といったものもある。

プロキシサーバやファイルのバックアップシステムにおいて不要なファイルの保存や転送を省略するためにはフィンガープリントが使用されるが、ここでの衝突は、単に本来ならば必要なかったはずの転送が必要になったというような結果であれば問題ないが、場合によっては不適切な処理やデータ消失の原因になりうる。暗号学的ハッシュ関数などを使うとかなり低い確率になるかもしれないが、それでもその可能性を考慮すべきかは難しい所である。

暗号分野の応用では衝突が致命的なものもあり、暗号学的ハッシュ関数と呼ばれる特別な一分野としてさかんに研究されている。この分野ではハッシュ関数について「弱衝突耐性」「強衝突耐性」といった術語が定義されており、暗号学的ハッシュ関数はこれらについて、目的に応じて必要な強度を満たしていることが求められる。

ハッシュ関数の結果

あるデータに対して何らかの変換関数(ハッシュ関数という)を適用して、そのデータに対するレコード位置(アドレスなどでもよい)を対応させることにする。このとき、別々のデータに対して同じレコード位置が対応する場合、「シノニムが生じる」などという。

例えば、データ「1,5,7,12,13」があり、データ値に対応するレコード位置を求める関数を「データ値を11で割った余り」ということにする。

データ レコード位置
1 1
5 5
7 7
12 1
13 2

この例でデータとレコード位置を表にすると上の通りである。

データが1と12のどちらもレコード位置が1になってしまっている。これを「データ1と12で(レコード位置の)シノニムが生じる」などという言い方をする。情報処理においては、シノニムが生じた場合の処理、もしくはシノニムをそもそも発生させない処理方法を予め考えておくことは必須である。


「衝突 (計算機科学)」の例文・使い方・用例・文例

Weblio日本語例文用例辞書はプログラムで機械的に例文を生成しているため、不適切な項目が含まれていることもあります。ご了承くださいませ。


英和和英テキスト翻訳>> Weblio翻訳
英語⇒日本語日本語⇒英語
  

辞書ショートカット

すべての辞書の索引

「衝突 (計算機科学)」の関連用語

衝突 (計算機科学)のお隣キーワード
検索ランキング

   

英語⇒日本語
日本語⇒英語
   



衝突 (計算機科学)のページの著作権
Weblio 辞書 情報提供元は 参加元一覧 にて確認できます。

   
ウィキペディアウィキペディア
All text is available under the terms of the GNU Free Documentation License.
この記事は、ウィキペディアの衝突 (計算機科学) (改訂履歴)の記事を複製、再配布したものにあたり、GNU Free Documentation Licenseというライセンスの下で提供されています。 Weblio辞書に掲載されているウィキペディアの記事も、全てGNU Free Documentation Licenseの元に提供されております。
Tanaka Corpusのコンテンツは、特に明示されている場合を除いて、次のライセンスに従います:
 Creative Commons Attribution (CC-BY) 2.0 France.
この対訳データはCreative Commons Attribution 3.0 Unportedでライセンスされています。
浜島書店 Catch a Wave
Copyright © 1995-2025 Hamajima Shoten, Publishers. All rights reserved.
株式会社ベネッセコーポレーション株式会社ベネッセコーポレーション
Copyright © Benesse Holdings, Inc. All rights reserved.
研究社研究社
Copyright (c) 1995-2025 Kenkyusha Co., Ltd. All rights reserved.
日本語WordNet日本語WordNet
日本語ワードネット1.1版 (C) 情報通信研究機構, 2009-2010 License All rights reserved.
WordNet 3.0 Copyright 2006 by Princeton University. All rights reserved. License
日外アソシエーツ株式会社日外アソシエーツ株式会社
Copyright (C) 1994- Nichigai Associates, Inc., All rights reserved.
「斎藤和英大辞典」斎藤秀三郎著、日外アソシエーツ辞書編集部編
EDRDGEDRDG
This page uses the JMdict dictionary files. These files are the property of the Electronic Dictionary Research and Development Group, and are used in conformance with the Group's licence.

©2025 GRAS Group, Inc.RSS