יום ראשון, 26 בפברואר 2012

Search Engine Spider

תמיד חשבתי לעצמי איך Google עושים את זה ובכלל איך מנועי חיפוש עובדים, החלטתי לעשות מחקר שיסביר איך בדיוק מנוע חיפוש עובד ואיך ניתן לממש אותו בעצמנו.

נעים להכיר - עכביש (Spider).
Spider - זו תוכנית שרצה לה ברחבי האינטרנט וקוראת את תוכן ה HTML ומפרקת אותו לחלקי מפתח ע"י החוקים שתכננו לה מראש כשבסוף המידע שנאסף נאגר במסדי נתונים ענקיים שבהם הלקוחות עושים את החיפושים, תהליך בניית ה Spider יכול להפוך למורכב מאוד ובתוכו חוקים רבים לגבי חיתוך דפי Html, במאמר זה נעבור בקצרה כיצד לממש מנוע חיפוש בעצמנו ונכיר את המנגנונים שבו.

באיזה פלטפורמה ניתן לממש Spider?
האמת היא שרוב השפות מאפשרות לנו יצירת Spider , ניתן גם להשתמש בשפות Scripts לדוגמה Perl , החלטתי להשתמש בפלטפורה של .Net שניתן לממש בה Spider בפשטות.

יופי טופי אבל בואו נדבר תכלס, בעצם מדובר בסוג של כדור שלג, תחילה טוענים Url ראשוני ל Spider  ולאחר מכן ה Spider מתחיל לעבוד, תחילה הוא מבצע Request לדף וממתין ל Response מהשרת, כשמגיע ה Response הוא מכיל את קוד ה Html , ה Spider מתחיל לחתוך חלקים מה Html בעזרת Regular Expression (נעבור עליהם בהמשך) ובסוף הוא אוגר רשימת Links (לדוגמה תגיות href) , כשמסתיים תהליך העיבוד הוא עובר ל Link הבא וכך הלאה.



שלב א: יצירת חיבור וקבלת Html.

 public string Html(string incomingCharset,string incomingWebsite)
        {
            try
            {
                if (incomingCharset != "")
                {
                    WebClient Client = new WebClient();
                    string Temphtml = "";
                    Client.Encoding = Encoding.GetEncoding(incomingCharset);
                    Temphtml = Client.Encoding.GetString(Client.DownloadData(incomingWebsite));
                    Client.CancelAsync();
                    return Temphtml;
                }
                else
                    return "";
            }
            catch (Exception ex)
            {
                return "";
            }
         
       
        }

הפונקציה תחזיר לנו את ה Html המלא של הדף בעזרת 2 פרמטרים , הפרמטר הראשון הוא ה CharSet עבור קידוד הטקסט לדוגמה: Windows-1252 , והשני הוא הכתובת של האתר שאנחנו רוצים לסרוק לדוגמה:  http://www.google.co.il/, בסיום התהליך יהיה לנו את ה Html עליו נבצע מניפולציות בעזרת Regular Expression.

 שלב ב: ביטויים רגולרים
ביטויים רגולרים (Regular Expression) הם בעצם סוגים של Patterns שמאפשרים לבצע חיתוכים על מחרוזות בצורה מהירה ויעילה לדוגמה: בדיקת תקינות ל Email, מספר טלפון, ת"ז וכו', אני לא אפרט על צורת הכתיבה של ביטויים רגולרים כי זה עולם ומלואו (למי שלא יכול להתאפק אפשר להתחיל כאן)  אבל אני מקווה להקדיש זמן בעתיד עבור נושא מרתק זה.

ריכזתי מספר Patterns מעניינים עבור ה Spider שלנו:

 public string MetaData(string IncomingHtml)
{
return new Regex("content\\s*=\\s*(?:\"(?<1>[^\"]*)\"|(?<1>\\S+))", RegexOptions.IgnoreCase).Match(IncomingHtml).Value.Trim();
}
* מחזיר תגית Metadata.

public string Title(string IncomingHtml)
{
return new Regex("(?<=<title.*>)([\\s\\S]*)(?=</title>)", RegexOptions.IgnoreCase).Match(IncomingHtml).Value.Trim();
}
* מחזיר תגית Title.

public string H1(string IncomingHtml)
{
return Regex.Replace(new Regex("(?<=<h1.*>)([\\s\\S]*)(?=</h1>)", RegexOptions.IgnoreCase).Match(IncomingHtml).Value.Trim(), "<.*?>", string.Empty).Trim();
}
* מחזיר תגית H1.

public string H2(string IncomingHtml)
{
return Regex.Replace(new Regex("(?<=<h2.*>)([\\s\\S]*)(?=</h2>)", RegexOptions.IgnoreCase).Match(IncomingHtml).Value.Trim(), "<.*?>", string.Empty).Trim();
}
* מחזיר תגית H2.

public string P(string IncomingHtml)
{
return Regex.Replace(new Regex("(?<=<p.*>)([\\s\\S]*)(?=</p>)", RegexOptions.IgnoreCase).Match(IncomingHtml).Value.Trim(), "<.*?>", string.Empty).Trim();
}
* מחזיר תגית P.

public string TD(string IncomingHtml)
{
return Regex.Replace(new Regex("(?<=<td.*>)([\\s\\S]*)(?=</td>)", RegexOptions.IgnoreCase).Match(IncomingHtml).Value.Trim(), "<.*?>", string.Empty).Trim();
}
* מחזיר תגית TD.

הבעיה עם סוג כזה של Pattern שהוא תמיד יחזיר לנו רק ערך אחד, מה יקרה אם נרצה להחזיר מערך מלא של כל הלינקים בדף? במקרה זה נשתמש ב Patterm הבא:

public ArrayList HRefs(string incomingHtml)
    {
      ArrayList arrayList = new ArrayList();
      string pattern = "href\\s*=\\s*(?:\"(?<1>[^\"]*)\"|(?<1>\\S+))";
      for (Match match = Regex.Match(incomingHtml, pattern, RegexOptions.IgnoreCase | RegexOptions.Compiled); match.Success; match = match.NextMatch())
      {
        string str = match.Groups[1].Value;
        arrayList.Add((object) str);
      }
      return arrayList;
    }

* אפשר להשתמש ב Pattern זה גם על שאר התגיות שכבר ראינו.

שלב ג: ריכוז לאובייקט מרכזי ורישום ל Database
זהו, אפשר להגיד שאנחנו לקראת הסוף, בשלב זה אנחנו נרכז את החוקים שאנחנו רוצים להגדיר ל Spider לחפש, פשוט נעביר את ה Html המקורי שלנו מחוק לחוק ונקלוט את הפלט לאובייקט מרכזי שאותו נרשום ב Database, אפשר להגיד שבשלב זה טמון כל הקסם וכנראה בגלל זה Google נמצאים איפה שהם בעזרת החוקים והמניפולציות שהם מפעילים על התוכן של האתרים.

סיכום (קצר מאוד):
אז מה ראינו? שמימוש של מנוע חיפוש הוא לא בשמיים מבחינה תכנותית אבל מאוד אדגרי בכל הקשור למסד הנתונים, שמירת מיליונים של חיתוכים ומניפולציות על עמודי Html מצריך חומרה חזקה ותחזוקה רצינית, במאמר זה עברנו על הטכניקה הבסיסית למימוש מנועי חיפוש.

בהצלחה במכה!

יום שבת, 18 בפברואר 2012

Android Application



למאמר הפתיחה בנוגע סביבת הפיתוח של Android לחץ כאן.

אז עד עכשיו עברתי על איך לבנות את הסביבת פיתוח עבור Android, אבל לפני שנתחיל לבנות את האפליקציה הראשונה שלנו כדאי להכיר את מערכת ההפעלה עצמה ואת השכבות ממנה היא בנויה, כמו כל מערכת הפעלה גם Android מחולקת לשכבות:




Hardware:

החומרה משתנה מיצרן ליצרן, בד"כ מדובר על מעבד אפליקטיבי לדוגמה Arm Cortex A9 ,  רכיב MMU - Management Memory Unit לטיפול במספר תהליכים במקביל, תמיד יהיה שטח אכסון ו Ram על מנת להריץ אפליקציות ואת מערכת ההפעלה.

Kernel:

במקרה של Android בסיס מערכת ההפעלה מבוסס על Kernel של Linux שבעצם נותן לנו אל כל השירותים עבור המערכת ומחבר אותנו לרכיבי החומרה במכשיר, ה Kernel עבר מספר שינויים ע"י גוגל, קודם כל זה לא לינוקס מלא וחלק מהכלים של לינוקס לא נמצאים, נמצאים בו כלים יחודיים עבור Android לדוגמה: Paranoid network-ing , שירות שמפריד לנו את הרשת ומאפשר רק לקבוצות מסויימות לבצע תקשורות כמו Bluetooth או לפתוח Sockets, דוגמה נוספת כלי ה Binder שהוא IPC ( inter process communication) יחודי עבור Android והרשימה עוד ארוכה - לחץ כאן לרשימה המלאה.





Native Libraries:

ספריית ה Api שמקשרת את האפליקציה ל Kernel , מכילה מספר ספריות לודגמה: Webkit שהוא שרת Http פנימי שבעזרתו ניתן לממש אפליקציות ב Html 5, ספריות גרפיות כמו Open GL, ממסד נתונים מסוג SqLite ועוד, בעזרת ספריות אלו ניתן לממש אפליקציות וליצור קשר עם החומרה ב Kernel.



 Runtime:

אמרתי כבר של Android כותבים ב Java? זאת השכבה הוירטואלית שיוצרת "חדר נקי" עבור אפליקציות, נותנת לאפליקציה שלנו תאימות , ועבודה עם קבצי Jar שמומרים בזמן ריצה לקבצי Dex בינארים שרצים בסביבה הוירטואלית.



Framework:

בשכבה הזאת רוב האפליקציות כתובות ורוב הזמן מבלים בשכבה הזאת, בעצם מהשכבה הזאת הכל מתחיל ומתגלגל דרך ה Runtime משם לספריות ובסוף ל Kernel.



מספיק עם התאוריה ונעבור לתכלס , קיימות 2 שיטות ליצירת אפליקציות ב Android ,השיטה הראשונה כתיבת אפליקציה ב Native Language של Android כלומר כתיבה  ב Java או כתיבת אפליקציה בעזרת Html 5 , ההבדל העיקרי הוא בהרשאות גישה לרכיבים במכשיר, בשיטה הראשונה אנחנו יכולים לגשת לאיזו חומרה שאנחנו רוצים וכמובן גישה לאחסון שעל המכשיר, בשיטה השניה יש הגבלות ולא ניתן לבצע את כל הדברים שהשיטה הראשונה מאפשרת לכן חשוב מאוד לאפיין את אופי האפליקציה וע"פ זה לבחור את השיטה המתאימה.

יצירת פרויקט חדש:




הגדרת שם לפרויקט



בחירת Api מתאים למכשיר (Galaxy s2 במקרה שלי)



הגדרת שם לחבילה של התוכנית - מקביל ל Namespace ב .Net , כלומר כל Class שניצור יהיה חלק מהחבילה הזאת.


לא משנה באיזו שיטה נבחר, הגדרת הפרויקט נעשת באותה שיטה, לאחר סיום התהליך נוצר הפרויקט שמכיל מספר תיקיות ומספר קבצים שנעבור עליהם בקצרה.

AndroidManifest.xml
קובץ הפרויקט שמכיל בתוכו את כל ה Activities , הרשאות , גרסאות וכו'.

תיקיית Res 
מכילה את כל ה Resources של התוכנית , תמונות בגרסאות שונות, אנימציות וכו`, בתוך תקייה זו קיימות מספר תיקיות נוספות , סדרת תיקיות Drawable שבה נאחסן את הקבצים הגרפיים שלנו לפי איכות , תיקיית ה Layout שבה מאוחסנים קבצי Xml של ה Gui, תיקיית Values מכילה קבצי ערכים קבועים,  במקרה של ריבוי שפות ניתן ליצר קובץ Value עובר כל שפה, יש גם תיקיות שנצטרך להוסיף ידנית כמו Anim שאחראית לכל קבצי האנימציה בתוכנית.

תיקיית Src
מכילה את ה Package שלנו, הקוד Java שלנו נמצא כאן.

תיקיית Assets
מכילה את קבצי Htnl ועובדת מול מנגון ה Webkit.



שיטה ראשונה:

Main.xml

<?xml version="1.0" encoding="utf-8"?>
<LinearLayout xmlns:android="http://schemas.android.com/apk/res/android"
    android:layout_width="fill_parent"
    android:layout_height="fill_parent"
    android:orientation="vertical" >
    <TextView
        android:id="@+id/textView1"
        android:layout_width="wrap_content"
        android:layout_height="wrap_content"
        android:text="Large Text"
        android:textAppearance="?android:attr/textAppearanceLarge" /
    <Button
        android:id="@+id/button1"
        android:layout_width="match_parent"
        android:layout_height="wrap_content"
        android:text="Button" />
</LinearLayout>

Proxytype_blogActivity.java

package com.proxytype_blog.demo;
import android.app.Activity;
import android.os.Bundle;
import android.view.View;
import android.view.View.OnClickListener;
import android.widget.Button;
import android.widget.TextView;
public class Proxytype_blogActivity extends Activity {
/** Called when the activity is first created. */
@Override
public void onCreate(Bundle savedInstanceState) {
     super.onCreate(savedInstanceState);
     setContentView(R.layout.main);
     Button myv = (Button) findViewById(R.id.button1);
     myv.setOnClickListener(new OnClickListener() {
         @Override
          public void onClick(View v) {
          TextView myc = (TextView) findViewById(R.id.textView1);
          myc.setText("hello world");
          }
     });
   }
}

תוצאה סופית:



שיטה שניה:
נוסיף תיקייה ל assets בשם www וניצור קובץ בשם index.htm ו script.js, שימו לב גם בשיטה זו יש התערבות של Java אבל היא מינורית, ה Java קורא לדף הראשון של האפליקציה ומשם היא מתגלגלת.

Main.xml

<?xml version="1.0" encoding="utf-8"?>
<LinearLayout xmlns:android="http://schemas.android.com/apk/res/android"
android:layout_width="fill_parent"
android:layout_height="fill_parent"
android:orientation="vertical" >
<WebView
android:id="@+id/WebView1"
android:layout_width="fill_parent"
android:layout_height="fill_parent"/>
</LinearLayout>

Proxytype_blogActivity.java

package com.proxytype_blog.demo;
import android.app.Activity;
import android.os.Bundle;
import android.webkit.WebChromeClient;
import android.webkit.WebView;
    public class Proxytype_blogActivity extends Activity {
    /** Called when the activity is first created. */
    @Override
        public void onCreate(Bundle savedInstanceState) {
        super.onCreate(savedInstanceState);
        setContentView(R.layout.main);
        WebView myv = (WebView)findViewById(R.id.WebView1);
        myv.getSettings().setJavaScriptEnabled(true);
        myv.setWebChromeClient(new WebChromeClient());
        myv.loadUrl(file:///android_asset/www/index.htm);
   }
}

Index.html

<!DOCTYPE html>
<html>
<head>
      <script src="script.js"></script>
</head>
<body>
       <button onclick="clickme()">Click Me</button>
</body>
</html>

script.js

 function clickme()
{
    alert('hello world!');
}

תוצאה סופית:



בהצלחה...

יום שבת, 4 בפברואר 2012

Linux Embedded System




לאחרונה רכשתי לוח פיתוח עבור Linux, מבוסס על מעבדי ARM , על מנת לפתח עליו אפליקציות יעודיות, עם מסך מגע, רשת ושאר תוספות, תהליך החיפוש ענק ויש המון יצרנים שיתנו לכם כמעט כל וריאציה של לוח כמו TI , FreeScale ועוד וכמובן ה Open Hardware שמוכרים מערכות פיתוח כמעט כמו של השחקנים הרציניים בפחות כסף לדוגמה: PandaBoard ו BeagleBoard , בסופו של דבר בחרתי בחברת Technexion חברה קטנה מטיוואן שנתנה לי לוח ומסך מגע במחיר סביר.

משהו חשוב שכדאי לכם לזכור לפני שאתם רצים לקנות לוח , כדאי לבדוק את היצרן ולראות שהוא נותן את כל הכלים שצריכים בשביל לבנות את המערכת  כמו Kernel , U-Boot, FileSystem וכמובן Documentation.

מאמר זה מתאר תהליך  בסיסי של בניית מערכת Embedded על לוח של חברת Technexion , אבל התהליך משותף לכל הלוחות , בכל לוח יש מספר רכיבים קבועים עבור הפעלת המערכת, הראשון הוא ה U-Boot שיטען לנו את ה Kernel לזיכרון ולאחר מכן FileSystem שמנהל לנו את הקבצים.

המימוש של התהליך משתנה מלוח ללוח במקרה שלי נוספו לי עוד מספר תוספות בתהליך הכוללים שינוי המיתוג ע"ג הלוח על מנת לעבוד עם מסך 7 אינץ, הורדת כלי נוסף X-Loader , שיטען את ה U-Boot לזיכרון, שינוי הגדרות בקבצי הקונפיגורציה ,יצירת דרייברים נוספים עבור החומרה בזמן יצירת ה Kernel ומיקום הקבצים ב SDCard, אומנם הרבה תוספות אבל בעזרת ה User Guide של היצרן נקבל את כל המידע הדרוש בשביל השלמת התהליך ולרוב הם מפורטים מאוד.


הכנת ToolChain:

על מנת להתחיל לעבוד על הלוח יש לבצע מספר הכנות מקדימות, תחילה יש להוריד את ה ToolChain של ARM שמכיל בתוכו קבוצת כלים - ASM/Debugger/Compiler , יש 2 חברות שמספקות ToolChain עבור מעבדי ARM,הראשונה היא CodeSorcery והשנייה FSF - free software foundation.

נפרוס את ה ToolChain לאיזה תיקיה שנרצה לאחר מכן יש להגדיר את התיקיה כנתיב חיפוש חדש למערכת ההפעלה שלנו, יש לערוך את קובץ
#:  gedit root/.bash_profile

שימו לב! התהליך מבוסס על OpenSuse בחלק מה Distributions שם הקובץ שונה לדוגמה ב ubuntu הוא נקרא bashrc.

נוסיף את נתיב החיפוש בצורה הבאה:

PATH="/opt/armsystem/CodeSourcery/Sourcery_G++_Lite/bin:${PATH}"export PATH

עכשיו מגיע החלק הקריטי בינינו ליצרן, בשלב זה נוריד מהיצרן את ה Kernel , U-Boot וה FileSystem המתאים ללוח שלנו, מרבית היצרנים דואגים לתת חבילות מסודרות שכוללות את כל הכלים עבור הלוח, יש לחפש באתר היצרן.

כחלק מהתהליך יש עבודה עם קבצי Makefile ועבור כל כלי יש את ה Makefile שלו, צריך לדואג שמוגדרת הארכיטקטורה הנכונה וה Cross Compiler המתאים עבור יצירת הקובץ הבינארי, לכן יש לפתוח ואת הקבצים ולחפש את השורות הבאות:

ARCH  ?= arm
CROSS_COMPILE ?= arm-none-linux-gnueabi-

מגדירים את הארכיטקטורה ואת ה Compiler שנמצא ב ToolChain לדוגמא עריכה של קובץ ה Makefile של ה Kernel.



נעשה תהליך דומה בקבצי ה Makefile של ה u-boot וה x-loader.

בניית X-Loader

יש לפרוס את קובץ המקור של היצרן , ניכנס לתיקיית ה X-Loader ונכתוב את הפקודה הבאה:

make distclean && make tam3517_config && make -j 2

פקודה זו תייצר קובץ בינארי ספציפי עבור הגדרות הלוח Tam3517 בשם MLO שאחראי על טעינת ה U-Boot לזיכרון , ניתן למצוא הגדרות ללוחות נוספים של היצרן בתיקיה Board.


בניית U-boot 

יש לפרוס את קובץ המקור של היצרן , ניכנס לתיקיית ה U-Boot ונכתוב את הפקודה הבאה:

#: make distclean && make tam3517_config && make -j 2 tam3517

פקודה זאת מייצרת לנו קובץ u-boot.bin שמותאם ללוח Tam3517 של חברת Technexion, ניתן למצוא הגדרות ללוחות נוספים של היצרן בתיקיה Board של ה U-Boot, דבר נוסף שיש לבצע הוא להעתיק את הקובץ mkimage שנמצא בתיקיה Tools ב U-Boot לתיקית החיפוש שעשינו על מנת שנוכל ליצור ממנו uImage מה Kernel, לא לשכוח לתת הרשאות עבור הקובץ

#: chmod 775 mkimage

בניית ה Kernel

יש לפרוס את קובץ המקור של היצרן ניכנס לתיקיית ה Kernel ונכתוב את הפקודה הבאה:

 #: make distclean && make tam3517_twister_defconfig && make -j 2 uImage && make modules

פקודה זו תייצר לנו קובץ zImage של ה Kernel שיהפוך ל uImage שמתאים ל U-Boot עבור לוח Tam3517 , הגדרות ללוחות נוספים ניתן לראות בתיקיה arch/arm/configs , ה uImage נוצר לנו בתיקיה arch/arm/boot , בנוסף נוצרו דרייברים עבור הלוח שנמצאים בתיקיה Drivers שאותם נעתיק לתיקיית boot ב FileSystem , בכל שלב נוכל לערוך את ה Kernel שלנו בממשק נוח בעזרת הפקודה

#: make menuconfig





בניית BuildRoot

היצרן נותן להוריד גם את ה FileSystem שמתאים ללוח שאותו נעתיק עם שאר הקבצים הבינארים שיצרנו בכל התהליך לכרטיס SDCard שממנו הזיכרון של הלוח יטען את המערכת, המערכת של Tam3517 מבוססת על מערכת הקבצים של Angstrom Distribution , ניתן לבנות את מערכת הקבצים בעצמנו בעזרת כלי BuildRoot שמאפשר לנו לנהל בעצמנו את מערכת הקבצים.

תחילה יש להוריד את ה BuildRoot עצמו, יש להוריד מספר תוספות על מנת שנוכל לעשות Compile ל BuildRoot שלנו, הראשונה היא ספריית bison , השנייה היא ספריית ה flex והשלישית היא ספריית texinfo בעזרת הפקודה לדוגמה:

#: zypper textinfo 

ה Buildroot מגיע בעצמו עם ToolChain עבור מספר ארכיטקטורות , ניתן לערוך את ה Build Root בדומה ל Kernel, בתיקייה הפרוסה של ה Buildroot נרשום:

#: make menuconfig



בקטגוריה Package Selection for the target נוכל למצוא את כל הכלים של Linux , שנוכל לבחור בקפדנות ולייצר אותם עבור הארכיטקטורה המתאימה, בסיום הבנייה נוצרת תיקיית output שמכילה את מערך הקבצים והתיקיות של ה FileSystem.




בניית SDCard:

יצירת 2 Partitions ע"ג ה SDCard , הראשון יהיה מוגדר כ FAT ואליו נעתיק את קובץ ה MLO של X-Loader , את קובץ u-boot.bin של ה U-Boot ואת ה uImage של ה Kernel ,ה Partiton השני יהיה מוגדר כ EXT3 שאליו נעתיק את ה BuldRoot שיצרנו, למאמר בנושא יצירת Partition לחץ כאן.


סיכום:

בסופו של דבר מדובר בשיטה שמשתנה במימוש אבל דומה בתהליך עצמו, בכל לוח נצטרך לעבוד עם תוכנית שתעשה Boot ראשוני למערכת וטעינה של ה Kernel לזיכרון , אח"כ ה Kernel מתחבר ל FileSystem והמערכת תעלה, אבל כל לוח לגופו והרבה תלוי ביצרן, לא היה ניתן לסיים את התהליך ללא ה User Guide שמוביל אותך בכל הדרך בלעדיו זה גישוש באפלה ולכן חשוב לרכוש לוח שיש מאחוריו חברה שמשקיעה בתיעוד שלו.

בהצלחה.