近隣の人を検索する検索アルゴリズムの実現
5934 ワード
モバイル端末の普及に伴い、多くのアプリケーションがLBS機能に基づいており、近くの某某(レストラン、銀行、妹紙など)が利用されている.
基礎データには、一般的に目標位置の経緯度が保存されている.ユーザが提供する緯度を用いて,比較を行い,近傍にあるか否かを得る.
ターゲット:
近くのXXXを探して、近いから远いまで结果を返して、しかも结果の中で目标点との距离があります.
近くのXXXを探すために、方案は以下の通りです.
Geohashアルゴリズム;geohashは2次元の緯度を1次元の文字列に符号化できるアドレス符号化である.
以下に、具体的な実装例を示します.
例えば、成都永豊立交の符号化はwm 3 yr 31 d 2524である
メリット:
1、1つのフィールドを利用して、経緯度を記憶することができる.検索時にインデックスを1つだけ使用すると、より効率的です.
2、符号化されたプレフィックスはより大きな領域を表すことができ、近くのものを探すのに便利である.SQLでは、LIKE「wm 3 yr 3%」で、近くのすべての場所を検索できます.
3、符号化精度により座標をぼかし、プライバシー保護などができる.
欠点:距離とソートには二次演算が必要です(フィルタ結果で実行されますが、実は速いです)
具体的なアルゴリズムの手順は次のとおりです.
1、geohashの符号化アルゴリズム
成都永豊立交経緯度(30.635578104.031601)
1.1、緯度範囲(-90,90)は2つの区間(-90,0)、(0,90)に分けられ、目標緯度が前の区間にある場合は0、そうでない場合は1となる.
30.625265は(0,90)に属するため、符号化は1とする.
次に(0,90)を(0,45)、(45,90)の2つの区間に分け、39.9324は(0,45)に位置するので0と符号化され、
次に(0,45)を(0,22.5)、(22.5,45)の2つの区間に分け、39.9324は(22.5,45)に位置するので1と符号化され、
順次類推すると、永豊立交緯度符号化は101010111001001001010100となる.
1.2、経度も同様のアルゴリズムで(-180,180)を順次細分化し、(-180,0)、(0180)符号化11001001111110100110000000000
1.3、経緯度符号化を合併し、高から低まで、まず1つの経度を取り、もう1つの緯度を取る.結果1110010010011111101011100011000010110000001001000100000100
1.4、0-9、b-z(a,i,l,oを除く)の32文字でbase 32符号化を行い、wm 3 yr 31 d 2524の符号化を得た(30.635578104.031601).
11100 10011 00011 11110 10111 00011 00001 01100 00010 00101 00010 00100 => wm3yr31d2524
10進0 1 2 3 4 5 6 7 8 9 10 11 13 14 15
base32 0 1 2 3 4 5 6 7 8 9 b c d e f g
十進法16 17 18 19 20 21 22 24 25 26 27 29 31
base32 h j k m n p q r s t u v w x y z
2、具体的な一致策略
1、緯度と経度が入庫する時、データベースは新しく1フィールドのgeohashをプラスして、この点のgeohash値を記録します
2、近くを探して、SQLの中でLIKE‘wm 3 yr 3%’;この結果をキャッシュできます.小さな領域では、緯度を変更するためにデータベース・クエリーを再実行することはありません.
3、検索した有限な結果、例えば距離或いは並べ替えを要求する場合、距離公式と2次元データの並べ替えを利用することができる.この時も少量のデータで、すぐにできます.
基礎データには、一般的に目標位置の経緯度が保存されている.ユーザが提供する緯度を用いて,比較を行い,近傍にあるか否かを得る.
ターゲット:
近くのXXXを探して、近いから远いまで结果を返して、しかも结果の中で目标点との距离があります.
近くのXXXを探すために、方案は以下の通りです.
Geohashアルゴリズム;geohashは2次元の緯度を1次元の文字列に符号化できるアドレス符号化である.
以下に、具体的な実装例を示します.
例えば、成都永豊立交の符号化はwm 3 yr 31 d 2524である
メリット:
1、1つのフィールドを利用して、経緯度を記憶することができる.検索時にインデックスを1つだけ使用すると、より効率的です.
2、符号化されたプレフィックスはより大きな領域を表すことができ、近くのものを探すのに便利である.SQLでは、LIKE「wm 3 yr 3%」で、近くのすべての場所を検索できます.
3、符号化精度により座標をぼかし、プライバシー保護などができる.
欠点:距離とソートには二次演算が必要です(フィルタ結果で実行されますが、実は速いです)
具体的なアルゴリズムの手順は次のとおりです.
1、geohashの符号化アルゴリズム
成都永豊立交経緯度(30.635578104.031601)
1.1、緯度範囲(-90,90)は2つの区間(-90,0)、(0,90)に分けられ、目標緯度が前の区間にある場合は0、そうでない場合は1となる.
30.625265は(0,90)に属するため、符号化は1とする.
次に(0,90)を(0,45)、(45,90)の2つの区間に分け、39.9324は(0,45)に位置するので0と符号化され、
次に(0,45)を(0,22.5)、(22.5,45)の2つの区間に分け、39.9324は(22.5,45)に位置するので1と符号化され、
順次類推すると、永豊立交緯度符号化は101010111001001001010100となる.
1.2、経度も同様のアルゴリズムで(-180,180)を順次細分化し、(-180,0)、(0180)符号化11001001111110100110000000000
1.3、経緯度符号化を合併し、高から低まで、まず1つの経度を取り、もう1つの緯度を取る.結果1110010010011111101011100011000010110000001001000100000100
1.4、0-9、b-z(a,i,l,oを除く)の32文字でbase 32符号化を行い、wm 3 yr 31 d 2524の符号化を得た(30.635578104.031601).
11100 10011 00011 11110 10111 00011 00001 01100 00010 00101 00010 00100 => wm3yr31d2524
10進0 1 2 3 4 5 6 7 8 9 10 11 13 14 15
base32 0 1 2 3 4 5 6 7 8 9 b c d e f g
十進法16 17 18 19 20 21 22 24 25 26 27 29 31
base32 h j k m n p q r s t u v w x y z
2、具体的な一致策略
1、緯度と経度が入庫する時、データベースは新しく1フィールドのgeohashをプラスして、この点のgeohash値を記録します
2、近くを探して、SQLの中でLIKE‘wm 3 yr 3%’;この結果をキャッシュできます.小さな領域では、緯度を変更するためにデータベース・クエリーを再実行することはありません.
3、検索した有限な結果、例えば距離或いは並べ替えを要求する場合、距離公式と2次元データの並べ替えを利用することができる.この時も少量のデータで、すぐにできます.
import java.util.HashMap;
import java.util.Map;
public class GeoHashKit {
private static char[] base32 = { '0', '1', '2', '3', '4', '5', '6', '7', '8', '9', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'j', 'k', 'm', 'n', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z' };
private final static Map<Character, Integer> decodemap = new HashMap<Character, Integer>();
static {
int sz = base32.length;
for (int i = 0; i < sz; i++) {
decodemap.put(base32[i], i);
}
}
private static int precision = 10;
private static int[] bits = { 16, 8, 4, 2, 1 };
/**
*
* @param int precision ，
*
* */
public static void setPrecision(int precision) {
GeoHashKit.precision = precision;
}
public static double getPrecision(double x, double precision) {
double base = Math.pow(10, -precision);
double diff = x % base;
return x - diff;
}
public static String encode(double latitude, double longitude) {
double[] lat_interval = { -90.0, 90.0 };
double[] lon_interval = { -180.0, 180.0 };
StringBuilder geohash = new StringBuilder();
boolean is_even = true;
int bit = 0, ch = 0;
while (geohash.length() < precision) {
double mid = 0.0;
if (is_even) {
mid = (lon_interval[0] + lon_interval[1]) / 2;
if (longitude > mid) {
ch |= bits[bit];
lon_interval[0] = mid;
} else {
lon_interval[1] = mid;
}
} else {
mid = (lat_interval[0] + lat_interval[1]) / 2;
if (latitude > mid) {
ch |= bits[bit];
lat_interval[0] = mid;
} else {
lat_interval[1] = mid;
}
}
is_even = is_even ? false : true;
if (bit < 4) {
bit++;
} else {
geohash.append(base32[ch]);
bit = 0;
ch = 0;
}
}
return geohash.toString();
}
public static double[] decode(String geohash) {
double[] ge = decode_exactly(geohash);
double lat, lon, lat_err, lon_err;
lat = ge[0];
lon = ge[1];
lat_err = ge[2];
lon_err = ge[3];
double lat_precision = Math.max(1, Math.round(-Math.log10(lat_err))) - 1;
double lon_precision = Math.max(1, Math.round(-Math.log10(lon_err))) - 1;
lat = getPrecision(lat, lat_precision);
lon = getPrecision(lon, lon_precision);
return new double[] { lat, lon };
}
public static double[] decode_exactly(String geohash) {
double[] lat_interval = { -90.0, 90.0 };
double[] lon_interval = { -180.0, 180.0 };
double lat_err = 90.0;
double lon_err = 180.0;
boolean is_even = true;
int sz = geohash.length();
int bsz = bits.length;
double latitude, longitude;
for (int i = 0; i < sz; i++) {
int cd = decodemap.get(geohash.charAt(i));
for (int z = 0; z < bsz; z++) {
int mask = bits[z];
if (is_even) {
lon_err /= 2;
if ((cd & mask) != 0) {
lon_interval[0] = (lon_interval[0] + lon_interval[1]) / 2;
} else {
lon_interval[1] = (lon_interval[0] + lon_interval[1]) / 2;
}
} else {
lat_err /= 2;
if ((cd & mask) != 0) {
lat_interval[0] = (lat_interval[0] + lat_interval[1]) / 2;
} else {
lat_interval[1] = (lat_interval[0] + lat_interval[1]) / 2;
}
}
is_even = is_even ? false : true;
}
}
latitude = (lat_interval[0] + lat_interval[1]) / 2;
longitude = (lon_interval[0] + lon_interval[1]) / 2;
return new double[] { latitude, longitude, lat_err, lon_err };
}
public static void main(String[] args) {
GeoHashKit ghf = new GeoHashKit();
String gc1 = ghf.encode(31.277631, 120.53916300000003);
String gc2 = ghf.encode(51.4797, -0.0124);
System.out.println(gc1);
System.out.println(gc2);
double[] gd1 = ghf.decode(gc1);
double[] gd2 = ghf.decode(gc2);
System.out.println(gd1[0] + ", " + gd1[1]);
System.out.println(gd2[0] + ", " + gd2[1]);
}
}