سریعترین روش جستجو در بانک اطلاعاتی بزرگ (در کمترین زمان)

[reza1944]

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

[omid.mohamadi]

کل جدول رو می تونی تو DataTable لود کنی ، و چون DataTable تو رم قرار میگیره می تونی چندبار ازش استفاده کنی که سرعتش هم بیشتره . کند شدن سرعت بخاطر این که هر بار رکوردها رو از نو میخونی خوب چه کاریه تو رم ببره از تو رم بخون .

[reza1944]

دکمه تشکر و هم زدم و ممنون از راهنمایت ولی روش برچسب گذاری بنظرم بهترین روشه که بعد از استفاده از الگوریتهای مختلف به این نتیجه رسیدم

[FastCode]

سلام.
سوالی که پرسیدید در واقع یک tradeoff ه بین
CPU
RAM
HDD
وقت
حجم کد
flexibility
و و و

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

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


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

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

[alias136790]

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

[FastCode]

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

[reza1944]

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

[tooraj_azizi_1035]

با FullText Search کار کن.
http://msdn.microsoft.com/en-us/library/ms142571.aspx#queries

[FastCode]

با 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]

سلام
تاپیک کمی قدیمیه ولی یک پیشنهاد می دم نظرتون رو بگید

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

[ghasemloo]

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

[Bahram0110]

کد نویسی زیادی نداره.
بجز تفکیک کلمات بانک بر اساس حروف الفبا

[FastCode]

کد نویسی زیادی نداره.
بجز تفکیک کلمات بانک بر اساس حروف الفبا
راه بهتر خیلی زیاده.
برای نمونه جست و جو کنید B+ Tree

[mousa1992]

بهتره مطالعاتی در این (http://www.w3schools.com/sql/sql_create_index.asp) مورد داشته باشین
همون چیزیه که میخوای ;)

[FastCode]

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


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

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