Google+ Followers

2015年8月29日 星期六

Node.js 筆記 - 使用 Bloom Filter 實作大量 URL Checker/Filter (SPAM)

最近想要針對 UGC 資料進行過濾,首先要面對的就是 SPAM/18+ 資料,接著,沒想到聽到 Bloom Filter 字眼!這個學生時代就碰過的東西,竟然會被提及,就那把玩一下吧!對於 Bloom Filter 的用法需要留意一下,本身設計是用時間省空間的架構,並且有誤判的機率,只要用得恰當都還好啦。

有點久沒摸 node.js 了,就挑他來試試,立馬找到有人已經實作好了 XD https://www.npmjs.com/package/bloomfilter 我只好接著使用啦 :P

接著不知不覺就蹦出一個 url-spam-checker 了 :P 有需要想把玩的可以試試:

$ npm install url-spam-checker
$ vim test.js
var
sys = require('sys'),
path = require('path'),
url_spam_checker = require('url-spam-checker')
;

url_spam_checker.createServer([
function handle_resource(callback){
var ret = [];
ret.push('yahoo.com');
ret.push('google.com.tw');
callback(null, ret);
}
], 8000, sys.log, sys.log);
$ node test.js


就會在 8000 port 起了 HTTP server ,接著可以用 http://localhost:8000/?url=http://tw.yahoo.com 的方式測試,若存在會回傳 HTTP 200 OK,不存在則是 HTTP 404 NOT FOUND。

當要驗證的 URL = http://tw.yahoo.com 也會被判定 200 OK,因為這邊是檢驗 domain level 的,不是 hostname 而已,同理在 URL = http://yahoo.com.tw 則是 404 NOT FOUND。而上述 handle_resource 可以自行填寫,例如回傳個20萬筆也是 ok 的。

這邊在使用 Bloom Filter 時,其 bit space =  Pattern 數量 x 256,這是因為我設定 hash function 有 8 組,所以 256 = 2^8  囉。

有興趣可以參考這邊:https://www.npmjs.com/package/url-spam-checker

2015年8月21日 星期五

Javascript 開發筆記 - 透過 Google Maps Routing API 畫路徑 (Directions Service)

Google Maps Directions Service

使用 GPS Location 畫圖時,點太多太精細,容易畫很慢,點太少太粗糙時,發現畫出的線會很糟,例如截彎取直的現象。雖然正解應該是先把精細路徑畫出圖來用,例如每個 zoom level 都畫好路線圖,而非動態畫線、畫點。但就是想偷懶透過 Google Maps API 來畫圖 XD 因此就研究了一下 Directions Service:https://developers.google.com/maps/documentation/javascript/directions

2000個點

假設原路線共有 2000 個精細點,接著取 200 個 sample 點出來,接著想想看怎樣用 Google Maps API 來畫圖。如果單純把這兩百個點畫連線,就會出現截彎取直的現象,因此,想到 Google 導航,透過導航機制自動幫你把路線畫得服服貼貼,畢竟 GPS 收集時也還有誤差問題,真正要做的好,還得把 GPS 位置修到路徑上,有許多眉眉角角。

在使用 Google Maps Directions Service 時,要留意限制,例如有 OVER_QUERY_LIMIT、MAX_WAYPOINTS_EXCEEDED 等限制,不是你想做就可以做:

  • OVER_QUERY_LIMIT indicates the webpage has sent too many requests within the allowed time period.
  • MAX_WAYPOINTS_EXCEEDED indicates that too many DirectionsWaypoints were provided in the DirectionsRequest. The maximum allowed waypoints is 8, plus the origin, and destination. Google Maps API for Work customers are allowed 23 waypoints, plus the origin, and destination. Waypoints are not supported for transit directions.

因此,需要將 200 個點,切成若干次 request ,每一個 request 含頭尾只能有 8 個座標點,其中給予頭尾就可以導航了,而其中的 6 個中繼點只是可以精細導航路線不會飄走。大概是這樣的概念處理資料,200個點,以 8 個點為單位 = 25 次 requests ,會踩到 OVER_QUERY_LIMIT 。儘管可以再透過 call api 的頻率來解決,但我又偷懶把 200 個點限縮成 5~6 次的 requests,然後再連續的 GPS 中,透過平均個數抽 6 個點出來,讓一個 request 還是有八個點,只是更不精細。

總之,程式碼大概長這樣:

<html>
<head>
<script src="https://code.jquery.com/jquery-2.1.4.min.js"></script>
<script src="https://maps.googleapis.com/maps/api/js?signed_in=true&callback=initMap" async defer></script>
<script>
var routes = [];
var points = [];
function initMap() {
var map = new google.maps.Map(document.getElementById('map'), {
zoom: 15,
center: {lat: 23.900422, lng: 121.603807}
});

var prev = null;
for (var i=0, cnt=data['results'].length; i<cnt ; ++i) {
var point = new google.maps.LatLng(data['results'][i]['location'].lat,data['results'][i]['location'].lng);
points.push({
location: point,
stopover: false, // 是否顯示
});

// add marker
if (0) {
var marker = new google.maps.Marker({
map: map,
position: point,
});
}
if (prev) {
// use multiple routes
routes.push({
origin: prev,
destination: point,
travelMode: google.maps.TravelMode.DRIVING
});
}
prev = point;
}

var directionsService = new google.maps.DirectionsService;
// multiple routes
// https://developers.google.com/maps/documentation/javascript/directions
if (0) {
for (var i=0, cnt=routes.length ; i<cnt ; ++i) {
console.log(i);
directionsService.route(routes[i], function(result, status) {
if (status == google.maps.DirectionsStatus.OK) {
var directionsDisplay = new google.maps.DirectionsRenderer({
suppressMarkers: true
});
directionsDisplay.setMap(map);
directionsDisplay.setDirections(result);
}
} );
}
}

// use multiple stops
// https://developers.google.com/maps/documentation/javascript/directions#Waypoints
var max_steps = 36;
for (var i=0, cnt=points.length; i < cnt ; i += max_steps) {
var stops = []; // max should be 8
var next_stop = Math.floor(max_steps / (8-2) );
for (var j=i+next_stop ; j<(max_steps - next_stop) && j < (cnt - 1) ; j += next_stop)  // 去頭去尾, 頭擺在 origin
stops.push(points[j]);
var request = {
origin: points[i].location,
destination: i+(max_steps - 1) < cnt ? points[i+max_steps-1].location : points[cnt-1].location,
waypoints: stops,
travelMode: google.maps.TravelMode.DRIVING,
};
directionsService.route(request, function(result, status) {
if (status == google.maps.DirectionsStatus.OK) {
var directionsDisplay = new google.maps.DirectionsRenderer({
suppressMarkers: true // 單純畫路線,不要顯示 marker
});
directionsDisplay.setMap(map);
directionsDisplay.setDirections(result);
} else {
console.log( status ); // OVER_QUERY_LIMIT, MAX_WAYPOINTS_EXCEEDED
}
} );
}
}

var data =
{
  "results": [
      {
         "elevation" : 17.00912857055664,
         "location" : {
            "lat" : 23.900397,
            "lng" : 121.603762
         },
         "resolution" : 610.8129272460938
      },
      {
         "elevation" : 20.88261413574219,
         "location" : {
            "lat" : 23.898869,
            "lng" : 121.603903
         },
         "resolution" : 610.8129272460938
      },
      {
         "elevation" : 22.29166030883789,
         "location" : {
            "lat" : 23.896661,
            "lng" : 121.60384
         },
         "resolution" : 610.8129272460938
      },
      {
         "elevation" : 20.24537467956543,
         "location" : {
            "lat" : 23.895185,
            "lng" : 121.60387
         },
         "resolution" : 610.8129272460938
      },
      {
         "elevation" : 30.49811744689941,
         "location" : {
            "lat" : 23.891678,
            "lng" : 121.603371
         },
         "resolution" : 610.8129272460938
      },
      // ...
   ]
};
</script>
</head>
<body>
<div id="map" style="width:100%; height:100%;"></div>
</body>
</html>

2015年8月17日 星期一

風雨生信心

風雨生信心

不知不覺參加了第三次了吧?第一次參加 COSCUP 用工作人員的角色,隔年則是一般會眾,今年偷懶不搶票,用 Open Source 貢獻者拿到票 XD

最近工作上的角色也有點蛻變,漸漸地不是用純工程師的角度思考、面對問題,更能專注一些生涯細節,稱不上轉職。至於八卦消息?永遠都一直充斥著生活,聽聽就好,畢竟永遠都是別人吃麵,聽八卦的喊燙。非常感謝老闆時常的棒頭當喝,抽出一點時間分享彼此看待事情的觀感,這樣的經歷給我不少的成長。

那生活的目標?重心?大概就是家人為主,多看看稚嫩的臉龐,著實是一種幸福啊。

或許下次參加時,又是用另一個嶄新的身份吧!

2015年8月8日 星期六

iOS 開發筆記 - 呼叫外部程式來處理一些資源(URL Scheme)

把一些 resource 轉交給外部程式,常見的就是 URL Scheme 技巧。

已知 URL scheme ,判斷是否支援:

if ([[UIApplication sharedApplication] canOpenURL:url])
    [[UIApplication sharedApplication] openURL:url];


若是 file:// 開頭的,可以用這試試:

UIDocumentInteractionController *dic = [UIDocumentInteractionController interactionControllerWithURL:url];
[dic presentOptionsMenuFromRect:self.view.bounds inView:self.view animated:YES];


其他,可以用這試試:

UIActivityViewController *avc = [[UIActivityViewController alloc] initWithActivityItems:@[url] applicationActivities:nil];
[self presentViewController:avc animated:YES completion:nil];

2015年8月1日 星期六

使用 jq、awk、sort、uniq、tail、diff、comm 處理 JSON 大檔

跟朋友相約參加了黑客松,主要是分析 SPAM 資訊,由於官方提供的是一個很大檔案的 json format,大多操作都適用 jq 指令處理,盡量不寫 code 來分析 XD

首先,只對指定欄位取出資料:

$ cat data_set.input
[
   { "field1":"1" , "field2": "2", "field3": 3, "field4" : [1, 2, 3] } ,
   { "field1":"a" , "field2": "b", "field3": 4, "field4" : [1, 2] } ,
   ...
}


$ < data_set.file jq '.[] | .field1 +"-" + .field2 '
"1-2"
"a-b"
...


有時會碰到資料欄位是 number ,這時會出現 string and number cannot be added 的部分,可以這樣做:

$ < data_set.input jq '.[] | .field1 +"-" + (.field3 | tostring) '
"1-3"
"a-4"
...


有時想看某個欄位個數:

$ < data_set.input jq '.[] | .field1 +"-" + (.field4 | length | tostring) '
"1-3"
"a-2"
...


接著偷懶用 awk 整理資料:

$ < data_set.file jq '.[] | .field1 +"-" + .field2 ' | awk -F'"' '{print $2}'
1-2
a-b
...


有時需要判斷數值大小後,來決定是否輸出:

$ < data_set.file awk -F'-' '{ if($2 > 10) { print $1 }}'

輸出後,可以透過 sort 跟 uniq 整理一下:

$ < data_set.file awk -F'-' '{ if($2 > 10) { print $1 }}' | sort | uniq

有時搭配 uniq -c 計算屬性後,再用 sort -n 來排序:

$ < data_set.file awk -F'-' '{ if($2 > 10) { print $1 }}' | sort | uniq -c | sort -n

這時,輸出的結果就有指定屬性從小排到大的特性,如果第 1234 個 line 開始是你要的資料,可以搭配 tail 指令取出:

$ < data_set.file awk -F'-' '{ if($2 > 10) { print $1 }}' | sort | uniq -c | sort -n | tail -n +1234

甚至,取出後再搭配 awk 把前置數字去除,只要重要結果即可:

$ < data_set.file awk -F'-' '{ if($2 > 10) { print $1 }}' | sort | uniq -c | sort -n | tail -n +1234 | awk -F ' ' '{print $2}'

最後,如果有 lookup_pattern 跟 check_data 想要比對,記得都要把兩者做 sort,就可以用 diff 跟 comm 兩個指令:

$ sort lookup_pattern > lookup_pattern.sorted
$ sort check_data > check_data.sorted


這時想要檢查沒有落在 lookup_pattern.sorted 的清單或個數:

$ diff lookup_pattern.sorted check_data.sorted | grep "<"
$ diff lookup_pattern.sorted check_data.sorted | grep -c "<"


那如果想看有 match 到的清單:

$ comm -1 -2 lookup_pattern.sorted check_data.sorted

如此一來就類似作為清單比對的動作。若比較的條件太多時,只好寫寫 python 啦:

#!/usr/bin/python
#
# input.log、p1.log、p2.log 都是以 line 為單位的資料
#

in_data = open('input.log').read().split("\n")

pattern_data1 = open('p1.log').read().split("\n")
pattern_data2 = open('p2.log').read().split("\n")

lookup1 = {}
for i in pattern_data1:
        lookup1[i] = ''

lookup2 = {}
for i in pattern_data2:
        lookup2[i] = ''

for i in in_data:
    if i in lookup1:
         print " data in lookup1"
    elif i in lookup2:
         print " data in lookup2 && not in lookup1"