當前位置：首頁 > 编程资源 > 编程问答 >内容正文

编程问答

Solr空间搜索原理分析与实践

發布時間：2024/7/5 编程问答 40 豆豆

生活随笔收集整理的這篇文章主要介紹了 Solr空间搜索原理分析与实践小編覺得挺不錯的,現在分享給大家,幫大家做個參考.

前言

在美團CRM系統中，搜索商家的效率與公司的銷售額息息相關，為了讓BD們更便捷又直觀地去搜索商家，美團CRM技術團隊基于Solr提供了空間搜索功能，其中移動端周邊商家搜索和PC端的地圖模式搜索功能為BD們的日常工作帶來了很大的便利，大大提升了BD們的工作效率。

在本文中，首先對空間搜索的原理進行簡單介紹，然后再結合具體的業務場景去分享美團使用空間搜索的實踐。

空間搜索原理

空間搜索，又名Spatial Search，基于空間搜索技術，可以做到：

1）對Point（經緯度）和其他的幾何圖形建索引 2）根據距離排序 3）根據矩形，圓形或者其他的幾何形狀過濾搜索結果

在Solr中，空間搜索主要基于GeoHash和Cartesian Tiers 2個概念來實現：

GeoHash算法

通過GeoHash算法，可以將經緯度的二維坐標變成一個可排序、可比較的的字符串編碼。在編碼中的每個字符代表一個區域，并且前面的字符是后面字符的父區域。其算法的過程如下：

根據經緯度計算GeoHash二進制編碼

地球緯度區間是[-90,90]，如某緯度是39.92324，可以通過下面算法對39.92324進行逼近編碼:

1）區間[-90,90]進行二分為[-90,0),[0,90]，稱為左右區間，可以確定39.92324屬于右區間[0,90]，給標記為1；

2）接著將區間[0,90]進行二分為 [0,45),[45,90]，可以確定39.92324屬于左區間 [0,45)，給標記為0；

3）遞歸上述過程39.92324總是屬于某個區間[a,b]。隨著每次迭代區間[a,b]總在縮小，并越來越逼近39.928167；

4）如果給定的緯度（39.92324）屬于左區間，則記錄0，如果屬于右區間則記錄1，這樣隨著算法的進行會產生一個序列1011 1000 1100 0111 1001，序列的長度跟給定的區間劃分次數有關。

同理，地球經度區間是[-180,180]，對經度116.3906進行編碼的過程也類似：

組碼

通過上述計算，緯度產生的編碼為1011 1000 1100 0111 1001，經度產生的編碼為1101 0010 1100 0100 0100。偶數位放經度，奇數位放緯度，把2串編碼組合生成新串：11100 11101 00100 01111 00000 01101 01011 00001。

最后使用用0-9、b-z（去掉a, i, l, o）這32個字母進行base32編碼，首先將11100 11101 00100 01111 00000 01101 01011 00001轉成十進制 28，29，4，15，0，13，11，1，十進制對應的編碼就是wx4g0ec1。同理，將編碼轉換成經緯度的解碼算法與之相反，具體不再贅述。

由上可知，字符串越長，表示的范圍越精確。當GeoHash base32編碼長度為8時，精度在19米左右，而當編碼長度為9時，精度在2米左右，編碼長度需要根據數據情況進行選擇。不過從GeoHash的編碼算法中可以看出它的一個缺點，位于邊界兩側的兩點，雖然十分接近，但編碼會完全不同。實際應用中，可以同時搜索該點所在區域的其他八個區域的點，即可解決這個問題。

Cartesian Tiers 笛卡爾層

笛卡爾分層模型的思想是將經緯度轉換成更大粒度的分層網格，該模型創建了很多的地理層，每一層在前一層的基礎上細化切分粒度，每一個網格被分配一個ID，代表一個地理位置。

每層以2的平方遞增，所以第一層為4個網格，第二層為16 個，所以整個地圖的經緯度將在每層的網格中體現：

那么如何構建這樣的索引結構呢，其實很簡單，只需要對應笛卡爾層的層數來構建域即可,一個域或坐標對應多個tiers層次。也即是tiers0->field_0，tiers1->field_1,tiers2-field_2,……，tiers19->field_19。（一般20層即可）。每個對應笛卡爾層次的域將根據當前這條記錄的經緯度通過笛卡爾算法計算出歸屬于當前層的網格，然后將gridId（網格唯一標示）以term的方式存入索引。這樣每條記錄關于笛卡爾0-19的域將都會有一個gridId對應起來。但是查詢的時候一般是需要查周邊的地址，那么可能周邊的范圍超過一個網格的范圍，那么實際操作過程是根據經緯度和一個距離確定出需要涉及查詢的從19-0（從高往低查）若干層對應的若干網格的數據。那么一個經緯度周邊地址的查詢只需要如下圖圓圈內的數據：

由上可知，基于Cartesian Tier的搜索步驟為： 1、根據Cartesian Tier層獲得坐標點的地理位置gridId 2、與系統索引gridId匹配計算 3、計算結果集與目標坐標點的距離返回特定范圍內的結果集合

使用笛卡爾層，能有效縮減少過濾范圍，快速定位坐標點。

基于Solr的空間搜索實踐

在Solr中，針對上述的2種原理提供了不同的索引方式去實現，分別是GeohashPrefixTree類和QuadPrefixTree類，其中GeohashPrefixTree對應GeoHash算法(也采用了笛卡爾層的分層思想)，QuadPrefixTree對應笛卡爾層的實現。

GeohashPrefixTree與QuadPrefixTree都繼承SpatialPrefixTree這個前綴樹基類，都使用了分層策略，主要索引和查詢邏輯?樣。不同點在于它們的maxLevels不一樣，獲取子cell的方式不一樣，GeohashPrefixTree有32個子cell(編碼為0-z)，QuadPrefixTree 只有有4個子cell(編碼為ABCD。A：左上，B：右上，C：左下，D：右下)。

而在Solr中，默認是使用GeohashPrefixTree的方式，索引下面重點介紹geohash的方式。利用Solr來實現空間搜索主要分為2部分：

1）索引的構建 2）查詢

索引構建

Step1 定義空間索引類型和字段

在Solr中提供了scheme.xml文件用來定義索引類型和字段，如下所示：

對于重要的屬性說明如下：

SpatialRecursivePrefixTreeFieldType

用于深度遍歷前綴樹的FieldType，主要用于獲得基于Lucene中的RecursivePrefixTreeStrategy。

JtsSpatialContextFactory

當有Polygon多邊形或者linestrings線段時，會使用jts(需要把jts.jar放到solr服務的lib下)，而基本形狀使用SpatialContext (spatial4j的類)。

distErrPct

定義非Point圖形的精度，范圍在0-0.5之間。該值決定了非Point的圖形索引或查詢時的level(如geohash模式時就是geohash編碼的長度)。當為0時取maxLevels，即精度最大,精度越大將花費更多的空間和時間去建索引。

geo

默認為true，值為true的情況下坐標基于球面坐標系，采用Geohash的方式；值為false的情況下坐標基于2D平面的坐標系，采用Euclidean/Cartesian的方式。

worldBounds

世界坐標值：”minX minY maxX maxY”。 geo=true即geohash模式時，該值默認為”-180 -90 180 90”。geo=false即quad時，該值為Java double類型的正負邊界，此時需要指定該值，設置成”-180 -90 180 90”。

distCalculator

設置距離計算算法，geo=true默認是haversine，geo=false默認是cartesian(笛卡爾計算方式)，值可以為”lawOfCosines”(余弦定理), “vincentySphere”(文森特球面公式) 或 “cartesian^2”。

prefixTree

Solr將地球映射為網格，prefixTree定義了網格的實現方式，每個網格在下一層中可以分解成多個子網格，geo=true prefixTree只能取GeoHash，geo=false prefixTree可取quad(quadTree一種四分樹地理位置索引，對應笛卡爾分層策略)

maxDistErr/maxLevels

maxDistErr定義了索引數據的最高層maxLevels，上述定義為0.000009，根據GeohashUtils.lookupHashLenForWidthHeight(0.000009, 0.000009)算出編碼長度為11位，精度在1米左右，直接決定了Point索引的term數。 maxLevels優先級高于maxDistErr,即有maxLevels的話maxDistErr失效。詳見SpatialPrefixTreeFactory.init()方法。不過一般使用maxDistErr。

units

單位是degrees，不適用于geofilt, bbox, or geodist（單位為km）

Step2 構建索引

構建索引代碼示例（在美團主要使用Point類型的索引）：

doc.setField(”poi_location_p", "32.52162,120.31778") //point類型或者 doc.setField("poi_location_p", "POLYGON((120.35330414772034 31.58268495951037,120.35190939903259 31.57923921490961,120.35330414772034 31.58268495951037))") //多邊形類型

構建流程：

下面主要說明Point類型的term創建過程。

1、將空間索引域的shapeStr解析成相應的Shape（這里指Point，復雜Shape如Polygon要使用JTS中的WTKReader來解析）。

2、創建索引域,具體過程參考org.apache.lucene.spatial.prefix.RecursivePrefixTreeStrategy中的createIndexableFields方法。

a、根據distErrPct字段，計算距離的誤差值，對于Point來說默認為0（而對于非Point類型來說，是通過外包矩形中心點到矩形頂點的距離再乘以distErrPct來計算誤差值的）

double distErr = SpatialArgs.calcDistanceFromErrPct(shape, distErrPct, ctx);public static double calcDistanceFromErrPct(Shape shape, double distErrPct, SpatialContext ctx) {if (distErrPct < 0 || distErrPct > 0.5) {throw new IllegalArgumentException("distErrPct " + distErrPct + " must be between [0 to 0.5]");}if (distErrPct == 0 || shape instanceof Point) {return 0;}Rectangle bbox = shape.getBoundingBox();//Compute the distance from the center to a corner. Because the distance// to a bottom corner vs a top corner can vary in a geospatial scenario,// take the closest one (greater precision).Point ctr = bbox.getCenter();double y = (ctr.getY() >= 0 ? bbox.getMaxY() : bbox.getMinY());double diagonalDist = ctx.getDistCalc().distance(ctr, bbox.getMaxX(), y);return diagonalDist * distErrPct; }

b、根據上述計算出的誤差值，得到索引的geohash編碼長度，對于Point類型來說值為maxLevels。

public int getLevelForDistance(double dist) {if (dist == 0)return maxLevels;//short circuitfinal int level = GeohashUtils.lookupHashLenForWidthHeight(dist, dist);return Math.max(Math.min(level, maxLevels), 1); }

c、根據編碼長度得到滿足所有條件的cells（每個cell表示一個前綴值），并將Cells都放在CellTokenStream中，同時構建索引域。Point類型每個Cell表示geohash的一個前綴值。

public List<Cell> getCells(Point p, int detailLevel, boolean inclParents){Cell cell = getCell(p, detailLevel);if (!inclParents) {return Collections.singletonList(cell);}String endToken = cell.getTokenString();assert endToken.length() == detailLevel;List<Cell> cells = new ArrayList<Cell>(detailLevel);for (int i = 1; i < detailLevel; i++) {cells.add(getCell(endToken.substring(0, i)));}cells.add(cell);return cells; }Field field = new Field(getFieldName(),new CellTokenStream(cells.iterator()), FIELD_TYPE);

3、構建存取域存儲索引

if (field.stored()) {if (shapeStr == null)shapeStr = shapeToString(shape);result.add(new StoredField(field.getName(), shapeStr)); }

4、結果

如經緯度41.79452,123.41555，對應的geohash為wxrvb2kqexu（maxLevels=11）, 則其對應的term有11個（如w、wx、wxr、wxrv…）。

查詢

查詢語法示例：

q={!geofilt pt=45.15,-93.85 sfield=poi_location_p d=5 score=distance} q={!bbox pt=45.15,-93.85 sfield=poi_location_p d=5 score=distance} q=poi_location_p:"Intersects(-74.093 41.042 -69.347 44.558)" //a bounding box (not in WKT) q=poi_location_p:"Intersects(POLYGON((-10 30, -40 40, -10 -20, 40 20, 0 0, -10 30)))" //a WKT example

涉及到的字段說明：

字段含義

q	查詢條件，如 q=poi_id:134567
fq	過濾條件，如 fq=store_name:農業
fl	返回字段，如fl=poi_id，store_name
pt	坐標點，如pt=54.729696,-98.525391
d	搜索半徑，如 d=10表示10km范圍內
sfield	指定坐標索引字段，如sfield=geo
defType	指定查詢類型可以取 dismax和edismax，edismax支持boos函數相乘作用，dismax是通過累加方式計算最后的score.
qf	指定權重字段：qf=store_name^10+poi_location_p^5
score	排序字段根據qf定義的字段defType定義的方式計算得到score排序輸出

其中有幾種常見的Solr支* 其中有幾種常見的Solr支持的幾何操作：

WITHIN：在內部
CONTAINS：包含關系
DISJOINT：不相交
Intersects：相交（存在交集）

日常常見的需求主要分為2類：

1. 范圍搜索（在美團CRM中對應周邊商家搜索）

范圍搜索支持2種范圍確定方式：

geofilt方式：根據搜索半徑過濾結果，返回以pt為圓心d為半徑的圓內所有點,如左圖所示返回圓形內所有點
bbox方式：根據具體的域過濾結果，不僅返回以pt為圓心d為半徑的圓內所有點，還包括域內其他點，返回矩形框內所有點，如下圖所示：

范圍搜索的情況很多，下面列舉一些常用場景的查詢語法：

不需要排序的場景
fq={!geofilt pt=45.15,-93.85 sfield=geo d=5}
fq={!bbox pt=45.15,-93.85 sfield=geo d=5}
需要排序的場景，較復雜

1) 按距離排序，距離越近排名越高，加上score=distance，其中distance是索引點到坐標點之間的弧度值，系統根據弧度值排序。

&fl=*,score&sort=score asc&q={!geofilt score=distance sfield=poi_location_p pt=54.729696,-98.525391 d=10}。

2) 按距離排序，距離越遠排名越高，加上score=reciDistance，其中reciDistance 范圍是0~1 采用倒數的方式計算，故與distance的排序剛好相反

&fl=*,score&sort=score asc&q={!geofilt score=reciDistance sfield=poi_location_p pt=54.729696,-98.525391 d=10}

3) 距離僅作排序不做過濾，在條件中設置filter=false，其中d只是確定形狀的作用,不起限制作用。

&fl=*,score&sort=score asc&q={!geofilt score=distance filter=false sfield=poi_location_p pt=54.729696,-98.525391 d=10}

4) 結合關鍵詞查詢和距離排序，此時關鍵字只能作為過濾條件（fq）不能作為查詢條件，僅作為過濾域。

&fl=*,score& fq=store_name:農業&sort=score asc&q={!geofilt score=distance sfield=poi_location_p pt=54.729696,-98.525391 d=10}

5) 當關鍵字和距離都作為排序條件時，可以用qf參數設置權重

&fl=*,score& fq=store_name:農業&sort=score asc&q={!geofilt score=distance sfield=poi_location_p pt=54.729696,-98.525391 d=10} &defType=dismax&qf=store_name^10+poi_location_p^5

2.圖形搜索（在美團CRM中對應地圖模式搜索）

在美團CRM中主要有以下幾種場景：

1) 直線附近1km商家搜索

&fl=*,score&sort=score asc&q=poi_location_p:"Intersects(LINESTRING(116.38263702392578 39.86653357724533,116.4935302734375 39.8578370694061) d=1

2) 正常多邊形范圍內的商家

&fl=*,score&sort=score asc&q=poi_location_p:"Intersects(POLYGON ((116.37714385986328 39.88392328618825,116.46709442138672 39.86627006289872,116.40392303466797 39.83358644035512,116.33525848388672 39.85124807212413,116.37714385986328 39.88392328618825))) distErrPct=0

3）復雜（如自相交）多邊形范圍內的商家

b 對于這種自相交的多邊形，Solr默認認為是非法的，會拋出類似這樣的異常： com.spatial4j.core.exception.InvalidShapeException: Self-intersection at or near point (116.4272689819336 39.875755941712825, NaN)，因此在將參數傳入solr前，需要基于標準 Douglas-Peucker Algorithm 算法對多邊形進行處理，處理后能去掉自相交的部分，效果如示意圖所示：

處理后，自相交的部分變為3和6兩個點。當然經過處理后的多邊形數據會損失一些精確度。

簡化前：

POLYGON((116.4272689819336 39.875755941712825,116.50142669677734 39.84966661865515,116.4059829711914 39.83068633533497,116.48357391357422 39.8873480121113,116.47808074951172 39.827258780634594,116.47773742675781 39.8177661982179,116.41319274902344 39.87048617098581,116.4272689819336 39.875755941712825))

簡化后：

POLYGON ((116.4272689819336 39.875755941712825,116.45455487823865 39.866156528285366, 116.48357391357422 39.8873480121113, 116.48079281261445 39.85692579689432,116.50142669677734 39.84966661865515,116.47973485573046 39.84535290095104,116.47808074951172 39.827258780634594,116.47773742675781 39.8177661982179,116.45096720829837 39.8396320628827,116.4059829711914 39.83068633533497,116.43551562011505 39.85225289138226,116.41319274902344 39.87048617098581,116.4272689819336 39.875755941712825)）

簡化后查詢語法變為：

&fl=*,score&sort=score asc&q=poi_location_p:"Intersects(POLYGON ((116.4272689819336 39.875755941712825,116.45455487823865 39.866156528285366, 116.48357391357422 39.8873480121113, 116.48079281261445 39.85692579689432,116.50142669677734 39.84966661865515,116.47973485573046 39.84535290095104,116.47808074951172 39.827258780634594,116.47773742675781 39.8177661982179,116.45096720829837 39.8396320628827,116.4059829711914 39.83068633533497,116.43551562011505 39.85225289138226,116.41319274902344 39.87048617098581,116.4272689819336 39.875755941712825)) distErrPct=0

無論是范圍查詢還是圖形搜索，他們的查詢基本流程都類似，主要分為下面2步：

1、解析查詢，生成Query樹：獲得相應的QParse（SpatialFilterQParser），對查詢串進行語法解析，獲得查詢串的各個參數，并且獲得相應的查詢Query（包括相應的Filter），其中也計算了查詢Shape的一些屬性，如最大索引長度detailLevel。

Query result = null;if (type instanceof SpatialQueryable) {double radius = localParams.getDouble(SpatialParams.SPHERE_RADIUS, DistanceUtils.EARTH_MEAN_RADIUS_KM);SpatialOptions opts = new SpatialOptions(pointStr, dist, sf, measStr, radius);opts.bbox = bbox;result = ((SpatialQueryable)type).createSpatialQuery(this, opts);}

2、查詢：SolrIndexSearch.search()進行創建Weight樹和Score樹，利用不同的filter和score策略得到符合條件的docIdSet。而對于幾種不同的幾何圖形關系，Solr提供了幾種不同的filter類來計算，這些filter都繼承AbstractPrefixTreeFilter類，簡單來說就是獲取與查詢Shape相交的所有子Cell，然后再與term進行匹配的過程。

總結

本文詳細分析了空間搜索的原理以及基于Solr的實踐，隨著移動互聯網時代的到來以及lbs技術的普及，空間搜索技術的應用場景會越來越多，同時隨著美團的不斷發展壯大，越來越多的商家會加入美團這個平臺，對于空間搜索的挑戰也將越來越大，此文僅僅作為拋磚引玉，空間搜索技術還有很多值得深入挖掘的地方。

參考

http://wiki.apache.org/solr/SolrAdaptersForLuceneSpatial4
https://cwiki.apache.org/confluence/display/solr/Spatial+Search#SpatialSearch-SpatialRecursivePrefixTreeFieldType(abbreviatedasRPT)
http://lucene.apache.org/
http://zh.wikipedia.org/wiki/%E9%81%93%E6%A0%BC%E6%8B%89%E6%96%AF-%E6%99%AE%E5%85%8B%E7%AE%97%E6%B3%95
http://www.vividsolutions.com/jts/JTSHome.htm
http://en.wikipedia.org/wiki/Well-known_text
https://github.com/spatial4j/spatial4j
http://dataknocker.github.io/2014/04/11/solr%E7%A9%BA%E9%97%B4%E7%B4%A2%E5%BC%95%E5%8E%9F%E7%90%86%E5%8F%8A%E6%BA%90%E7%A0%81%E5%88%86%E6%9E%90/

總結

以上是生活随笔為你收集整理的Solr空间搜索原理分析与实践的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。

上一篇：百度高级Java三面题目！涵盖JVM +
下一篇：机器学习系列-强填EM算法在理论与工程之