PDA

View Full Version : حرفه ای: سریعترین روش جستجو در بانک اطلاعاتی بزرگ (در کمترین زمان)



reza1944
یک شنبه 25 تیر 1391, 22:53 عصر
سلام به دوستان
من یه جدول تو بانک اطلاعاتی با دو فیلد دارم که حدود 65000 لغت داره که میخوام بدون معطلی تو بانک از تریق کدم جستجو های پی در پی انجام بدم
کلا من یه مترجم متن نوشتم ولی سرعت ترجمه متنش پایینه به همین خاطر با چه الگوریتمی بدون معطی میتونم تو بانکم جستجو کنم. البته از بحث هوش مصنوعی و اینهاش بگزریم و فقط می خوام جستجوهای پی در پیم واقعا سریع و بی وقفه باشه
ممنون میشم راهنمایی کنید.

omid.mohamadi
یک شنبه 25 تیر 1391, 23:41 عصر
کل جدول رو می تونی تو DataTable لود کنی ، و چون DataTable تو رم قرار میگیره می تونی چندبار ازش استفاده کنی که سرعتش هم بیشتره . کند شدن سرعت بخاطر این که هر بار رکوردها رو از نو میخونی خوب چه کاریه تو رم ببره از تو رم بخون .

reza1944
یک شنبه 01 مرداد 1391, 21:05 عصر
دکمه تشکر و هم زدم و ممنون از راهنمایت ولی روش برچسب گذاری بنظرم بهترین روشه که بعد از استفاده از الگوریتهای مختلف به این نتیجه رسیدم

FastCode
یک شنبه 01 مرداد 1391, 21:53 عصر
سلام.
سوالی که پرسیدید در واقع یک tradeoff ه بین
CPU
RAM
HDD
وقت
حجم کد
flexibility
و و و

برای RAM میتونی به bitset نزدیک بشی
برای HDD میتونی اطلاعات رو فشرده کنی(اگر CPU مهم نیست حتی LZMA)
اگر وقت داشته باشی میتونی bitset رو با یه ساختار ه tree یا map ه دلخواه ترکیب کنی.
و البته همه این روش ها نیاز به تلاش فوق العاده زیاد داره.
این برنامه چقدر مهمه (از نظر صرفه برای مصرف ۶ مورد فوق) و

من شخصاً اگر چنین چیزی مینوشتم,
اول متن اصلی رو میخوندم و سورت میکردم و بعد دیتابیس سورت شده رو decompress میکردم و با هم scan میکردم
لیست کلمات در اومده رو در حافظه نگه میداشتم و اگر کلمات دیکشنری tag ه موضوع داشت کلمات اضافه رو حذف میکردم.
ترجمه شما آمادست.


اگر نیاز به راهنمایی دارید, سوالتون رو اینجا مطرح کنید و بعد PM بدید که ببینم.

اگر این کارفرمایان محترم دست از سر این ۶۰ تا فرمی که باید طراحی کنم بردارن خیلی دوست دارم یه نمونه بنویسم.پروژه جالبیه.

alias136790
دوشنبه 02 مرداد 1391, 02:05 صبح
سلام
میتونی یه قسمت برای برنامه ات بزاری که نوع جستجو رو کاربر تعیین کنه : عمومی ، فیزیک، شیمی، ادبیات،نجوم و...
این یعنی محدود کردن جستجو ،و بعد گروه بندی کردن لغات تو دیتابیس .
حالا موقعی که خواستی یه متن رو ترجمه کنی کافیه تو گروه عمومی و اون گروهی که کاربر تعیین کرده جستجو کنی مثلا
(عمومی و فیزیک) یا (عمومی و نجوم)یا ( عمومی و ادبیات)
به هر حال مطلب مهمتر تو ترجمه متن اینه که بعد از پیدا کردن لغات ، بتونی اونا رو سرهم بچینی و جمله بندی درست رو انجام بدی
و قواعد دستوری زبان مقصد رو هم بلد باشی(به مترجم نیاز داری )و البته بدون هوش مصنوعی ممکن نیست.

FastCode
دوشنبه 02 مرداد 1391, 02:47 صبح
سلام
میتونی یه قسمت برای برنامه ات بزاری که نوع جستجو رو کاربر تعیین کنه : عمومی ، فیزیک، شیمی، ادبیات،نجوم و...
این یعنی محدود کردن جستجو ،و بعد گروه بندی کردن لغات تو دیتابیس .
حالا موقعی که خواستی یه متن رو ترجمه کنی کافیه تو گروه عمومی و اون گروهی که کاربر تعیین کرده جستجو کنی مثلا
(عمومی و فیزیک) یا (عمومی و نجوم)یا ( عمومی و ادبیات)
به هر حال مطلب مهمتر تو ترجمه متن اینه که بعد از پیدا کردن لغات ، بتونی اونا رو سرهم بچینی و جمله بندی درست رو انجام بدی
و قواعد دستوری زبان مقصد رو هم بلد باشی(به مترجم نیاز داری )و البته بدون هوش مصنوعی ممکن نیست.
این روش اینطوری نیست.
هر کلمه ممکنه در هر رشته ای معنی متفاوتی بده.
به طور نمونه من راهکاری به شکل تگ معرفی کردم که هر معنی کلمه مربوط به یک دسته بشه و دسته ای که بیشترین تعداد کلمه رو داره به عنوان دسته غالب برای تعیین موضوع انتخاب بشه و بقیه معنی ها از حافظه حذف بشن.
نمونه متن
http://xkcd.com/1082/

reza1944
دوشنبه 02 مرداد 1391, 14:26 عصر
کلا من میخوام یه پروژه متن باز بنویسم که همه دوستان به میل خودشون تغییرش بدن و هر روز بهتره بشه و همه بتونن ازش استفاده کنن
در زمینه ترجمه متن و همچنین ocr فارسی. با بحث هوش مصنوعی هم تا یه اندازه ای آشنایی دارم

tooraj_azizi_1035
دوشنبه 02 مرداد 1391, 14:40 عصر
با FullText Search کار کن.
http://msdn.microsoft.com/en-us/library/ms142571.aspx#queries

FastCode
دوشنبه 02 مرداد 1391, 16:51 عصر
با FullText Search کار کن.
http://msdn.microsoft.com/en-us/library/ms142571.aspx#queries
چقدر این راه حل OSS ه.



//these can even be serialized with just anything but XML and .Net BinaryFormatter, not really important since we read these just once per run
public class Word {
string mValue;
string Value{ get { return mValue; } set { mValue = value; } }
int Compare (string obj) {
return mValue.CompareTo (obj);
}
Language mLanguage;
Language Language{ get { return mLanguage; } set { mLanguage = value; } }
System.Collections.Generic.Dictionary<Language,
System.Collections.Generic.Dictionary<Tag,
System.Collections.Generic.List<Word
>>>
mTranslations;

public System.Collections.Generic.Dictionary<Language, System.Collections.Generic.Dictionary<Tag, System.Collections.Generic.List<Word>>> Translations {
get {
return mTranslations;
}
set {
mTranslations = value;
}
}

public void AddTranslation (Language Language, Tag Tag, Word Word) {
//TODO: implement
}
public override string ToString () {
return mValue;
}
}
class Tag {
int mID;
string mName;

public int ID {
get {
return mID;
}
set {
mID = value;
}
}

public string Name {
get {
return mName;
}
set {
mName = value;
}
}

}
public class Language {
int mID;
string mName;
string mMSLocaleName;
string mPosixLocaleName;

public int ID {
get {
return mID;
}
set {
mID = value;
}
}
public string Name {
get {
return mName;
}
set {
mName = value;
}
}
public string MSLocaleName {
get {
return mMSLocaleName;
}
set {
mMSLocaleName = value;
}
}
public string PosixLocaleName {
get {
return mPosixLocaleName;
}
set {
mPosixLocaleName = value;
}
}

}

public class RefInt {
public int Value;
}
static class Translator {
///DictionaryData must be sorted, O(m*log(m));//it happens just once
public static string Translate (System.Collections.Generic.List<Word> DictionaryData, string Input, Language InputLanguage, Language DestinationLanguage) {
if (InputLanguage.ID == DestinationLanguage.ID) {
return Input;
}
//O(n)
string[] SplittedString = Input.Split (new char[]{' ', '\n', '\r'}, System.StringSplitOptions.RemoveEmptyEntries);
//O(n*log(n));//n is so small, it wont take more than a few MilliSecond to sort
Array.Sort (SplittedString);
//TODO: Remove dups in SplittedString

int DictionaryIndex;
int DictionaryLength;

//O(n+m)
System.Collections.Generic.Dictionary<Tag, RefInt> TagRepeats = new System.Collections.Generic.Dictionary<Tag, RefInt> ();
DictionaryIndex = 0;
DictionaryLength = DictionaryData.Count;
foreach (string S in SplittedString) {
int Comp = 1;
while (Comp <= 0) {
Word CurrentWord = DictionaryData [Index];
Comp = Word.CompareTo (S);
if (Comp > 0) {
//we have a missing word
#if DEBUG
Console.WriteLine("word '" + S + "' has no translation");
#endif
} else if (comp < 0) {
//Go next
} else {
//found

System.Collections.Generic.Dictionary<Tag, System.Collections.Generic.List<Word>> CurrentTags;

//check if it has a translation ins destination language
bool HasLanguage = CurrentWord.Translations.TryGetValue (InputLanguage, out CurrentTags);
if (HasLanguage) {
//small dictionary, K^2 won`t affect speed
foreach (System.Tuple<Tag, System.Collections.Generic.List<Word>> T in CurrentTags) {
RefInt TagRepeatCount;
bool HaveTag = TagRepeats.TryGetValue (T.Item1, out TagRepeatCount);
if (HaveTag) {
TagRepeatCount.Value++;
} else {
TagRepeats.Add (T.Item1, new RefInt (){Value =1});
}
}
}
}
}
}
//TODO: Sort TagRepeats in reverse RefInt Order

System.Collections.Generic.SortedDictionary<string, Word> Words = new System.Collections.Generic.SortedDictionary<string, Word> ();
DictionaryIndex = 0;
DictionaryLength = DictionaryData.Count;
foreach (string S in SplittedString) {
int Comp = 1;
while (Comp <= 0) {
Word CurrentWord = DictionaryData [Index];
Comp = Word.CompareTo (S);
if (Comp > 0) {
//we have a missing word
#if DEBUG
Console.WriteLine("word '" + S + "' has no translation");
#endif
} else if (comp < 0) {
//Go next
} else {
//found

System.Collections.Generic.Dictionary<Tag, System.Collections.Generic.List<Word>> CurrentTags;

//check if it has a translation ins destination language
bool HasLanguage = CurrentWord.Translations.TryGetValue (InputLanguage, out CurrentTags);
if (HasLanguage) {
//small dictionary, K^2 won`t affect speed
foreach (System.Tuple<Tag, System.Collections.Generic.List<Word>> T in CurrentTags) {
Word Meaning;
bool HaveMeaning = Words.TryGetValue (S, out Meaning);
if (HaveMeaning) {
//WTF
//TODO: panic
} else {
Word W;
//TODO set W = some word from T.Item2, and use most used tags list to determine which is best
Words.Add (S, W);
}
}
}
}
}
}

//Scan 'Input' and replace the words with items in 'Words'

}
}

//TODO: write some database storage backend,

Bahram0110
شنبه 16 شهریور 1392, 00:33 صبح
سلام
تاپیک کمی قدیمیه ولی یک پیشنهاد می دم نظرتون رو بگید

کلمات را بر اساس حروف الفبا در جدول های مختلف قرار بدیم. مثلا یک جدول برای A یک جدول برای B و ...
وقتی کاربر قصد جستجو دارد طبق اولین حرف کلمه وارد شده شروع به جستجو در همان جدول می کنیم. در این صورت جستجو بین تعداد بسیار کمتری کلمه صورت می گیره

ghasemloo
شنبه 16 شهریور 1392, 01:19 صبح
سلام
کلمات را بر اساس حروف الفبا در جدول های مختلف قرار بدیم. مثلا یک جدول برای A یک جدول برای B و ...
وقتی کاربر قصد جستجو دارد طبق اولین حرف کلمه وارد شده شروع به جستجو در همان جدول می کنیم. در این صورت جستجو بین تعداد بسیار کمتری کلمه صورت می گیره
روش جالبیه
اما کد نویسیش میره بالا

Bahram0110
یک شنبه 17 شهریور 1392, 01:12 صبح
کد نویسی زیادی نداره.
بجز تفکیک کلمات بانک بر اساس حروف الفبا

FastCode
یک شنبه 17 شهریور 1392, 01:40 صبح
کد نویسی زیادی نداره.
بجز تفکیک کلمات بانک بر اساس حروف الفبا
راه بهتر خیلی زیاده.
برای نمونه جست و جو کنید B+ Tree

mousa1992
یک شنبه 17 شهریور 1392, 01:46 صبح
بهتره مطالعاتی در این (http://www.w3schools.com/sql/sql_create_index.asp) مورد داشته باشین
همون چیزیه که میخوای ;)

FastCode
یک شنبه 17 شهریور 1392, 01:56 صبح
بهتره مطالعاتی در این (http://www.w3schools.com/sql/sql_create_index.asp) مورد داشته باشین
همون چیزیه که میخوای ;)
که از همون B+ Tree استفاده میکنه.


هر کسی که بعدا این تاپیک رو میخونه یک جست و جو در مورد انواع Bloom Filter و Rope هم بکنید.

احتمالا پارسال منظورم از bitSet همون Bloom Filter بوده که چون با BitSet پیاده سازی میشه اشتباه نوشتم.