バイナリデータを検索する方法(vb.net)

画像データなどのバイナリ化されたデータから特定の16進コードを検索する方法を紹介します。
今回のケースは、下記の様なバイナリデータから、「my-hobby」という文字列を含み、かつ「my-hobby」の後に「&HFF」(16進コードFF)が付くバイナリデータの最初のインデックスを取得する方法です。

検索対象とするバイナリデータの情報は下記の通りです。

上記の赤枠部分が今回検索したい箇所です。

ソースは下記の通り
[vbnet]
Imports System.IO

Dim ByteArray As Byte()
Dim TargetByte As Byte() = {&H6D, &H79, &H2D, &H68, &H6F, &H62, &H62, &H79, &HFF} ‘「my-hobby」を16進化したコードをセット(最後はFF)
Dim i As Integer
Dim ByteIndex As Integer
Dim StartIndex As Integer
Dim HitFLG As Boolean ‘True:検索文字列ヒット

ByteArray = File.ReadAllBytes(ファイルパス) ‘.net Framework 2.0以上対応
StartIndex = 0

Do
ByteIndex = Array.IndexOf(ByteArray, TargetByte(0), StartIndex) ‘最初の一文字を検索する
If ByteIndex < 0 Or StartIndex + TargetByte.Length – 1 >= ByteArray.Length Then
ByteIndex = -1
HitFLG = False
Exit Do ‘最初の文字が見つからなかった場合、またはStartIndexの位置がバイト配列の最後まで到達した場合は処理終了
Else
HitFLG = True ‘一時的にヒットの状態にする
End If

For i = 1 To TargetByte.Length – 1 ‘残りの文字(2文字目以降)も検索する
If ByteArray(ByteIndex + i) <> TargetByte(i) Then
HitFLG = False ‘1文字でも合致しなかったらFalseにセット
Exit For
End If
Next

If HitFLG = True Then
Exit Do ‘全ての文字がヒットしたら処理を抜ける
Else
StartIndex = ByteIndex + 1 ‘ヒットしなかった場合は、検索開始位置を1バイトずらして再度検索
End If
Loop

Console.Write(ByteIndex) ‘該当した文字列の1文字目の配列インデックスを出力する。-1の場合は該当する文字が無かった事を意味する。
[/vbnet]

上記の処理を実行すると、272 が出力されます。
なお、上記処理はInteger型の上限を超える容量のファイルを扱う事は出来ません。

ちなみに上記の検索アルゴリズムはクヌース-モリス-プラット法 – Wikipediaという方式に似ていますが、バイナリデータの保存形式、使用用途に応じて検索アルゴリズムを変えていく事で、より高速な検索が出来るのでは無いかと思います。
Category:検索アルゴリズム – Wikipediaを見ると、世の中には色んな検索アルゴリズムがある事が分かります。

まぁこの辺を意識しなくても検索できる、.net Frameworkが出来てくれると一番嬉しいんですが。。。

VB.NETの技術メモ~DBアクセスの高速化(バインド変数の使用)後編~

my-hobby : VB.NETの技術メモ~DBアクセスの高速化(バインド変数の使用)前編~では、DBアクセス時に動的にSQLを生成したケースと、バインド変数を使用してSQLを生成したケースを紹介しました。
本編では、計測結果を比較・検証したいと思います。

先ずは、動的にSQLを生成したケースの結果(処理時間)は以下の通りでした。
交互にそれぞれ3回同じ処理を行いました。
●1回目(動的にSQLを生成したケース)
[vbnet]
2010/01/19 21:09:13
2010/01/19 21:09:22:700000
[/vbnet]

●1回目(バインド変数を使用してSQLを生成したケース)
[vbnet]
2010/01/19 21:09:34
2010/01/19 21:09:42:700000
[/vbnet]

●2回目(動的にSQLを生成したケース)
[vbnet]
2010/01/19 21:10:23
2010/01/19 21:10:32:700000
[/vbnet]

●2回目(バインド変数を使用してSQLを生成したケース)
[vbnet]
2010/01/19 21:10:34
2010/01/19 21:10:41:700000
[/vbnet]

●3回目(動的にSQLを生成したケース)
[vbnet]
2010/01/19 21:11:11
2010/01/19 21:11:20:700000
[/vbnet]

●3回目(バインド変数を使用してSQLを生成したケース)
[vbnet]
2010/01/19 21:11:45
2010/01/19 21:11:52:700000
[/vbnet]
※2行目の700000という数字は、DBから郵便番号(7桁)が10万回読み込めた事を証明しています。

動的にSQLを生成したケースは平均9秒、バインド変数を使用してSQLを生成したケースは平均7.3秒。
う~ん微妙な感じ。。。
数件の処理でこの違いであれば、かなりの改善ということになりますが 、10万件の処理でこの結果ということは、今回のテストケース自体が簡単過ぎたからでしょうか?
もう少し複雑な処理や、数百万件という大量のデータを扱う様なケースであれば、更なるパフォーマンス向上が見込めるのかも知れません。
逆に言えばこの様な単純な処理でも、結果にここまで差が出た事は、それなりにパフォーマンス向上の効果が出たと言えるのではないでしょうか?

VB.NETの技術メモ~DBアクセスの高速化(バインド変数の使用)前編~

アプリケーションのパフォーマンスでボトルネックになりやすい要因の一つに、データベース(DB)へのアクセスがあります。
今回はDBへのアクセス(特にSQL文の発行)に関して、バインド変数を使ったパフォーマンス向上の方法を紹介し、それぞれの方法でどれだけパフォーマンスに違いが出るのかを検証してみたいと思います。
なお、前提事項として、以下の開発環境で検証をしました。
・言語:VB.NET
・フレームワーク:.NET Framework 2.0
・DBサーバ:SQL Server 2005 Express Edition

検証を行なうに当たり大量のデータが必要なので、zpnaviでもお世話になっている、郵便番号検索 – 日本郵便より提供されている住所データを使用します。
10万件の住所データに対して、1から順番にシーケンス番号を振ります。 そのデータを1件づつ読み込んで、10万件目が終わるまでの処理時間を計測します。

●動的にSQLを生成したケース
動的にSQLを生成したケースでは、以下の様に動的にSQL文を組み立てて、その内容に対してDBにSQLを発行します。

[vbnet]
Imports System.Data.SqlClient
Imports System.Text

sub Test()
Debug.Print(Now)

Dim SqlConn As New SqlConnection
Dim SqlCmd As SqlCommand
Dim SqlRd As SqlDataReader
Dim StSQL As String
Dim i As Long
Dim TownName As New StringBuilder

SqlConn.ConnectionString = "(DB接続文字列)"
SqlConn.Open()
SqlCmd = SqlConn.CreateCommand

For i = 1 To 100000
StSQL = "SELECT NEW_ZIP FROM T_ADDRESS WHERE SEQ = " & i
SqlCmd.CommandText = StSQL
SqlRd = SqlCmd.ExecuteReader
SqlRd.Read()
TownName.Append(SqlRd(0).ToString)
SqlRd.Close()
Next
SqlCmd.Dispose()
SqlConn.Close()
Debug.Print(Now & ":" & TownName.Length)

End Sub
[/vbnet]

●バインド変数を使用してSQLを生成したケース
[vbnet]
Imports System.Data.SqlClient
Imports System.Text
sub Test()
Debug.Print(Now)

Dim SqlConn As New SqlConnection
Dim SqlCmd As SqlCommand
Dim SqlPrm As SqlParameter
Dim SqlRd As SqlDataReader
Dim StSQL As String
Dim i As Long
Dim TownName As New StringBuilder

SqlConn.ConnectionString = "(DB接続文字列)"
SqlConn.Open()
SqlCmd = SqlConn.CreateCommand
SqlPrm = SqlCmd.Parameters.Add("@SEQ", SqlDbType.Int)
SqlPrm.Direction = ParameterDirection.Input
StSQL = "SELECT NEW_ZIP FROM T_ADDRESS WHERE SEQ = @SEQ"
SqlCmd.CommandText = StSQL

For i = 1 To 100000
SqlPrm.Value = i
SqlRd = SqlCmd.ExecuteReader
SqlRd.Read()
TownName.Append(SqlRd(0).ToString)
SqlRd.Close()
Next
SqlCmd.Dispose()
SqlConn.Close()
Debug.Print(Now & ":" & TownName.Length)
End Sub
[/vbnet]

なお、上記のプログラムを作成するに当たり、.NET アプリケーションのパフォーマンスとスケーラビリティの向上 – 第 12 章 「ADO.NET パフォーマンスの向上」を参考にしました。

前者と後者のプログラムの違いは、各プログラムの19行目のDBに発行するSQL文が動的か、固定かの違いです。

この様な実装方法にする理由はmsdnのサイトには記載されていませんでしたが、Oracleの場合でもバインド変数を使った実装の方が、パフォーマンスがいいと言われています。
具体的な理由もありました。

Oracle Database 10gがOracle Database 10gがSQL文を受け取った場合、共有プール(メモリ領域)をチェックして、文がすでに存在しメモリに格納されているかどうかを確認します。文がメモリに存在し、Oracle Database 10gがその文を再利用できる場合、データベースは文を解析および最適化するタスクをスキップできます。バインド変数を使用すると、SQL文がメモリに格納される可能性が大幅に高まります。これによって、そのSQL文を必要とする次の操作で迅速にそのSQL 文を使用できます。
※Oralceでバインド変数を使用する為には、「Oracle.DataAccess」コンポーネントを参照追加する必要があります。

上記の内容は、値のバインドの「バインド変数が重要な理由」より抜粋

SQL Serverの場合は上記の様な具体的な理由までは記述されていませんでしたが、恐らく同様の理由だと思います。

では動的にSQLを生成したケースと、バインド変数を使用してSQLを生成したケースとではどれくらいパフォーマンスに違いが出るのか?
結果はVB.NETの技術メモ~DBアクセスの高速化(バインド変数の使用)後編~ に掲載しています。

2地点の緯度経度から距離を求める(Goole MAPS API ~距離の計算式編~)

my-hobby : 2地点の緯度経度から距離を求める(Google MAPS APIとの比較~結果報告編~)の結果で、Google Maps API リファレンス – Google Maps API – Google Code(google方式)の精度が、3平方の定理を使用した方式(ろっきー方式)よりも精度が良い事が分かりました。
そこでgoogle方式の計算式を調べていたところ、偶然、javascriptのコードを緯度経度から2点の距離を求める – masakiplusの日記で見つけました。

今回は、これをVB.netに変換し、2点間の距離を算出しました。
以下のプログラムです。
[vbnet]
Imports System.Math
Public Function Getdistance(ByVal longitudeFrom As Double, ByVal latitudeFrom As Double, ByVal longitudeTo As Double, ByVal latitudeTo As Double)As Double
Dim from_x As Double ‘A地点の経度(ラジアン)
Dim from_y As Double ‘A地点の緯度(ラジアン)
Dim to_x As Double ‘B地点の経度(ラジアン)
Dim to_y As Double ‘B地点の緯度(ラジアン)
Dim deg As Double
Dim distance As Double ‘2地点の距離

from_x = longitudeFrom* Math.PI / 180
from_y = latitudeFrom * Math.PI / 180
to_x = longitudeTo * Math.PI / 180
to_y = latitudeTo * Math.PI / 180

deg = Sin(from_y) * Sin(to_y) + Cos(from_y) * Cos(to_y) * Cos(to_x – from_x)
distance = 6378140 * (Atan(-deg / Sqrt(-deg * deg + 1)) + Math.PI / 2) / 1000 ‘2地点の距離(Km)
Return distance

End Function
[/vbnet]

このプログラムを使用して、計算を行った結果と、google方式の結果を比較したところ、以下の様な結果となりました。

図1-計算結果
図1-計算結果

※赤がgoogle方式、黒がインターネット上で見つけた計算式です。
google方式、インターネット上で見つけた方式の順に上書き描画しています。

なんと黒色の点しか存在しません。

詳細に調べる為、結果を数値レベルで比較したところ、最も誤差の大きいところでも0.013Km程度でした。(0.00008%の誤差)
また、上記のケースは東経0~180度、北緯0~90度の範囲ですが、念の為に世界全体で比較した場合も同様の結果となりました。(図2を参照)

図2-計算結果(世界全体)
図2-計算結果(世界全体)

プログラムで小数点以下を扱う以上、この程度の誤差は出てしまうので、ほぼこの計算式で間違いないと言えます。

なおGoogle MAPS APIの公式な情報として、この計算式が発表されているわけでは無いので、本当の計算式は不明ですが、非常によく似た結果になった事は事実です。
今回は計5回に分けて記事を書きましたが、その結果以下の結論を得る事が出来ました。

・三平方の定理を使用した2地点の距離の計算式(ろっきー方式)よりは、Google MAPS APIが提供している機能(google方式)の方が精度が良い。
・図1、図2の様なテストケースにおいて、Google MAPS APIが提供している2地点の距離を求める計算結果は、上記の計算式を使用して計算した結果と非常によく似ている。

前者は悔しいですが、ある意味予想通りの結果でした。
ただ後者の事実が得られた事は予想外の収穫でした。

この計算式があれば、インターネットが利用できない環境(Google MAPS APIが利用できない環境)でも、Google MAPS APIを利用した場合と同等の結果(2地点の距離)を求めることが出来るようになります。

ちなみに余談ですが、計算式のヒントとして紹介したサイトから、更にそのサイトが参考にしたサイト(Seis Pesos)は、googleマップを使った技術がすごいです。
上記の計算式も、元々はこのサイトで掲載されていた様です。(今は無かったです)
今後googleマップを使ったアプリを作る機会があったら参考にしたいと思います。(今回のもう一つの収穫でした)

GoogleAPI~2つの住所から距離を求める~

前回までは、住所から緯度経度を取得する方法を紹介してきました。
前回の記事はmy-hobby : GoogleAPI~住所から緯度経度を取得する(その2)~に記載されています。

今回は2つの住所から、2点間のおおよその距離を測定する方法にチャレンジしてみたいと思います。
「おおよその距離」とはちょっと歯切れの悪い言い方ですが、
コレには理由があって、今回緯度経度を使って、2点間の距離を求める方法に
3平方の定理を使用するからです。

3平方の定理は、あくまで平面の世界において成立する定理であり、
地球の様に丸い(立体的な)物体に対しては正確な値は得られないので、
「おおよその距離」と表現しました。
ただ、日本の国土くらいの大きさならさほど誤差は出ないだろうという想定で、
今回この方法を使って実際に試してみたいと思います。

考え方は以下の通りです。
1.2地点の住所から緯度経度を求める。

2.2地点の緯度経度から、緯度差、経度差を求める。

経度差:139.7454109-135.5065076=4.2389033
緯度差:35.6586345-34.6524841=1.0061504

3.緯度差、経度差より、距離A、距離Bの距離を求める

距離A:4.2389033×111×cos34.6524841(※2)=387.0557915Km
距離B:1.0061504×111(※1)=111.6826944Km

※1については地球 – Wikipediaの「大きさ、質量、密度」に記載されている、以下の情報から経度、緯度それぞれの1度あたりの距離を算出しました。

赤道半径が6,378.137km、極半径が6,356.752km

計算式:半径×2×円周率÷360
実際の値(赤道半径):6,378.137km×2×3.14159÷360=111.3193968Km
実際の値(極半径):6,356.752km×2×3.14159÷360=110.9461584Km

上記の通り、地球は真円ではありませんが、これを考慮に入れると非常に計算式が難しくなるので、今回は地球を真円とみなし、1度あたりの距離も、111Kmで統一する事にします。

※2については、必ずしも1度あたりの距離が111Kmにはならないので、「cos34.6524841」はそれを補正する為の式となります。
詳細な説明は後日紹介します。

4.3平方の定理を使用し、距離Cを求める。

これらの内容をプログラムに組み込むと以下の様な感じになります。

■入力フォーム

■ソースコード

[vbnet]
Imports System.Xml
Imports System.Web
Imports System.Math

Public Class Form1
Private Sub btn_Search_Click(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles btn_Search.Click

Dim xNode As XmlNodeList
Dim Enc_Address As String
Dim APIKey As String = "(各自で取得したAPIキー)"
Dim RequestUrl As String
Dim GeoCode() As String

Dim IdoWK As Double
Dim KeidoWK As Double
Dim KyoriWK As Double
Dim CosIdoWK As Double

If txt_Address.Text = "" Then
Exit Sub
End If

‘住所1の緯度経度を取得
Enc_Address = HttpUtility.UrlEncode(txt_Address.Text)
RequestUrl = "http://maps.google.com/maps/geo?&amp;q=" &amp; Enc_Address &amp; "&amp;output=xml&amp;key=" &amp; APIKey

Dim xDoc As XmlDocument = New XmlDocument
xDoc.Load(RequestUrl)

Dim nsmgr As XmlNamespaceManager = New XmlNamespaceManager(xDoc.NameTable)
nsmgr.AddNamespace("gmap", "http://earth.google.com/kml/2.0")
xNode = xDoc.SelectNodes("/gmap:kml/gmap:Response/gmap:Status/gmap:code", nsmgr)

If xNode.Item(0).InnerText <> "200" Then
Exit Sub
End If

xNode = xDoc.SelectNodes("/gmap:kml/gmap:Response/gmap:Placemark/gmap:Point/gmap:coordinates", nsmgr)
GeoCode = Split(xNode.Item(0).InnerText, ",")
txt_Keido.Text = GeoCode(0)
txt_Ido.Text = GeoCode(1)

‘住所2の緯度経度取得
Enc_Address = HttpUtility.UrlEncode(txt_Address2.Text)
RequestUrl = "http://maps.google.com/maps/geo?&amp;q=" &amp; Enc_Address &amp; "&amp;output=xml&amp;key=" &amp; APIKey

xDoc.Load(RequestUrl)
xNode = xDoc.SelectNodes("/gmap:kml/gmap:Response/gmap:Status/gmap:code", nsmgr)

If xNode.Item(0).InnerText <> "200" Then
Exit Sub
End If

xNode = xDoc.SelectNodes("/gmap:kml/gmap:Response/gmap:Placemark/gmap:Point/gmap:coordinates", nsmgr)
GeoCode = Split(xNode.Item(0).InnerText, ",")
txt_Keido2.Text = GeoCode(0)
txt_Ido2.Text = GeoCode(1)

‘2地点の緯度経度より、距離を計算
If txt_Ido.Text < txt_Ido2.Text Then
CosIdoWK = txt_Ido.Text
Else
CosIdoWK = txt_Ido2.Text
End If

IdoWK = Abs(txt_Ido.Text – txt_Ido2.Text) * 111
KeidoWK = Abs(txt_Keido.Text – txt_Keido2.Text) * Cos(Math.PI / 180 * CosIdoWK) * 111
KyoriWK = (IdoWK ^ 2 + KeidoWK ^ 2) ^ (1 / 2)

txt_Kyori.Text = KyoriWK

End Sub
End Class
[/vbnet]

■実行結果

結果として、402.846385062963Km≒402.85Kmとなりました。
それでは測量計算(距離と方位角の計算)より実際の距離を測ってみたいと思います。

国土地理院のページなので、信頼性が高いと思い、このページで得られた結果を正解とします。
結果は401.99Kmとなりました。
誤差は0.86Km(0.2%の誤差)。予想以上に正確な値が出ました。

計算方法は「別途文献を見て下さい」との事でした。
「文献」と書いていある時点で難しそうなので、今回はここまでとします。

ちなみに、これを応用すれば、例えば日本全国の日帰り温泉の緯度経度情報を予め調べておき、ある地点から一番近い温泉を調べるといった事も出来るようになります。
GPSを搭載した携帯を持っていれば、郊外に出かけた際、ふと温泉に入りたくなった時に近場の日帰り温泉を探すのに便利ですね。。。

後日の調査で別の計算方式を載せた記事がありますので、よろしければ参考にしてください。
my-hobby : 2地点の緯度経度から距離を求める(Goole MAPS API ~距離の計算式編~)