Oprimized OCR خوارزمية البكسل الأسود / الأبيض

Question

أنا أكتب حل OCR بسيط لمجموعة محدودة من الشخصيات. هذا هو، أعرف الطريقة الدقيقة أن جميع الحروف 26 في الأبجدية ستبدو. أنا أستخدم C # وأنا قادر على تحديد ما إذا كان يجب التعامل مع بكسل معطى باللون الأسود أو الأبيض.

أنا أنظر مصفوفة من بكسلات سوداء / بيضاء لكل شخصية واحدة. لذلك على سبيل المثال، قد تبدو الرسالة الأولى (رأس المال الأول)، كما يلي:

01110
00100
00100
00100
01110

ملاحظة: جميع النقاط، التي أستخدمها لاحقا في هذا المنشور، افترض أن أعلى البكسل الأيسر هو (0، 0)، بكسل الأيمن السفلي (4، 4). 1 تمثل بكسلات سوداء، وتمثل 0 بكسل بيضاء.

أود إنشاء مصفوفة مقابلة في C # مثل هذا:

CreateLetter("I", new List<List<bool>>() {
  new List<bool>() { false, true,  true, true,  false },
  new List<bool>() { false, false, true, false, false },
  new List<bool>() { false, false, true, false, false },
  new List<bool>() { false, false, true, false, false },
  new List<bool>() { false, true,  true, true,  false }
});

أعلم أنني ربما يمكنني تحسين هذا الجزء باستخدام مجموعة متعددة الأبعاد بدلا من ذلك، لكن دعنا نتجاهل ذلك في الوقت الحالي، وهذا لأغراض توضيحية. كل حرف هو بالضبط نفس الأبعاد، 10 بكسل بواسطة 11px (10px by 11px هو الأبعاد الفعلية للشخصية في برنامجي الحقيقي. قمت بتبسيط هذا إلى 5 بكسل من 5 بكسل في هذا النشر لأنه أسهل بكثير "رسم" الحروف باستخدام 0 و 1 على صورة أصغر).

الآن عندما أعطيه 10px من قبل 11 بكسل جزء من صورة للتحليل مع OCR، ستحتاج إلى تشغيل كل حرف واحد (26) على كل بكسل واحد (10 * 11 = 110) مما يعني 2،860 (26 * 110) التكرارات (في أسوأ الحالات) لكل حرف واحد.

كنت أفكر في ذلك يمكن تحسينه من خلال تحديد الخصائص الفريدة لكل حرف. لذلك، على سبيل المثال، لنفترض أن مجموعة الأحرف تتكون فقط من 5 أحرف مميزة: I، A، O، B، و L. هذه قد تبدو وكأنها ما يلي:

01110  00100  00100  01100  01000
00100  01010  01010  01010  01000
00100  01110  01010  01100  01000
00100  01010  01010  01010  01000
01110  01010  00100  01100  01110

بعد تحليل الخصائص الفريدة لكل حرف، يمكنني تقليل عدد الاختبارات التي يجب إجراءها بشكل كبير للاختبار لشخصية. على سبيل المثال، بالنسبة لشخصية "أنا"، يمكنني تحديد خصائصها الفريدة بأنها وجود بكسل أسود في الإحداثيات (3، 0) نظرا لعدم وجود شخصيات أخرى بهذا بكسل أسود. بدلا من ذلك بدلا من اختبار 110 بكسل للمباراة على شخصية "i"، قللتها إلى اختبار 1 بكسل.

هذا هو ما قد يبدو عليه بكل هذه الشخصيات:

var LetterI = new OcrLetter() {
  Name = "I",
  BlackPixels = new List<Point>() { new Point (3, 0) }
}
var LetterA = new OcrLetter() {
  Name = "A",
  WhitePixels = new List<Point>() { new Point(2, 4) }
}
var LetterO = new OcrLetter() {
  Name = "O",
  BlackPixels = new List<Point>() { new Point(3, 2) },
  WhitePixels = new List<Point>() { new Point(2, 2) }
}
var LetterB = new OcrLetter() {
  Name = "B",
  BlackPixels = new List<Point>() { new Point(3, 1) },
  WhitePixels = new List<Point>() { new Point(3, 2) }
}
var LetterL = new OcrLetter() {
  Name = "L",
  BlackPixels = new List<Point>() { new Point(1, 1), new Point(3, 4) },
  WhitePixels = new List<Point>() { new Point(2, 2) }
}

هذا أمر صعب أن يفعل يدويا لمدة 5 أحرف وأصبح أصعب بكثير كمية الحروف التي تتم إضافتها. تريد أيضا ضمان أن يكون لديك الحد الأدنى لمجموعة من الخصائص الفريدة للحرف لأنك تريد أن يتم تحسينها قدر الإمكان.

أريد إنشاء خوارزمية من شأنها تحديد الخصائص الفريدة لجميع الحروف وسوف تولد رمز مشابه لذلك أعلاه. ثم استخدم هذه المصفوفة السوداء / البيضاء المحسنة لتحديد الأحرف.

كيف يمكنني تناول 26 حرفا تحتوي على كل بكسلاتها السوداء / البيضاء المملوءة (مثل كتلة رمز المكونات) وتحويلها إلى مجموعة محسنة من الخصائص الفريدة التي تحدد خطابا (مثل كتلة رمز OCRELTER () الجديد)؟ وكيف يمكنني أن أضمن أنها مجموعة تعريف أكثر كفاءة من الخصائص الفريدة (على سبيل المثال بدلا من تحديد 6 نقاط كخصائص فريدة، قد تكون هناك طريقة للقيام بذلك مع 1 أو 2 نقطة، كحرف "أنا" في بلدي مثال كان قادرا على).

---

الحل البديل الذي وصلت إليه هو استخدام جدول تجزئة، مما سيقلل منه من 2860 تكرارا إلى 110 تكرارا، وتخفيض 26 مرة. هذه هي الطريقة التي قد تعمل:

أود أن أملكها مع البيانات المشابهة لما يلي:

Letters["01110 00100 00100 00100 01110"] = "I";
Letters["00100 01010 01110 01010 01010"] = "A";
Letters["00100 01010 01010 01010 00100"] = "O";
Letters["01100 01010 01100 01010 01100"] = "B";

الآن عندما وصلت إلى موقع في الصورة معالجتها، أقوم بتحويله إلى سلسلة مثل: "01110 00100 00100 00100 00100 01110" وحده ببساطة في طاولة التجزئة. يبدو هذا الحل بسيطا للغاية، ومع ذلك، لا يزال هذا يتطلب 110 تكرارا لتوليد هذه السلسلة لكل حرف.

في تدوين كبير o، فإن الخوارزمية هي نفسها منذ O (110N) = O (2860N) = O (N) لأحرف N لمعالجة على الصفحة. ومع ذلك، ما زالت تحسنت من خلال عامل مستمر من 26، وهو تحسن كبير (على سبيل المثال، بدلا من ذلك يستغرق 26 دقيقة، سيستغرق الأمر دقيقة واحدة).

---

تحديث: معظم الحلول المقدمة حتى الآن لم تعالج مسألة تحديد الخصائص الفريدة للشخصية وتقديم حلول بديلة إلى حد ما. ما زلت أبحث عن هذا الحل الذي، بقدر ما أستطيع أن أقول، هو السبيل الوحيد لتحقيق أسرع معالجة الحروف التي تعكس.

لقد توصلت للتو بحل جزئي:

لكل بكسل، في الشبكة، قم بتخزين الحروف التي تحتوي على بكسل أسود.

باستخدام هذه الحروف:

  I      A      O      B      L
01110  00100  00100  01100  01000
00100  01010  01010  01010  01000
00100  01110  01010  01100  01000
00100  01010  01010  01010  01000
01110  01010  00100  01100  01110

سيكون لديك شيء من هذا القبيل:

CreatePixel(new Point(0, 0), new List<Char>() {                         });
CreatePixel(new Point(1, 0), new List<Char>() { 'I',           'B', 'L' });
CreatePixel(new Point(2, 0), new List<Char>() { 'I', 'A', 'O', 'B'      });
CreatePixel(new Point(3, 0), new List<Char>() { 'I'                     });
CreatePixel(new Point(4, 0), new List<Char>() {                         });
CreatePixel(new Point(0, 1), new List<Char>() {                         });
CreatePixel(new Point(1, 1), new List<Char>() {      'A',      'B', 'L' });
CreatePixel(new Point(2, 1), new List<Char>() { 'I'                     });
CreatePixel(new Point(3, 1), new List<Char>() {      'A', 'O', 'B'      });
// ...
CreatePixel(new Point(2, 2), new List<Char>() { 'I', 'A',      'B'      });
CreatePixel(new Point(3, 2), new List<Char>() {      'A', 'O'           });
// ...
CreatePixel(new Point(2, 4), new List<Char>() { 'I',      'O', 'B', 'L' });
CreatePixel(new Point(3, 4), new List<Char>() { 'I', 'A',           'L' });
CreatePixel(new Point(4, 4), new List<Char>() {                         });

الآن لكل حرف، من أجل العثور على الخصائص الفريدة، تحتاج إلى إلقاء نظرة على الدلاء التي تنتمي إليها، وكذلك كمية الشخصيات الأخرى في الجرافة. لذلك دعونا نأخذ مثال "أنا". نذهب إلى جميع الدلاء التي تنتمي إليها (1،0؛ 2،0؛ 3،0؛ ...؛ 3،4) ونرى أن واحد بأقل قدر من الشخصيات الأخرى (3،0). في الواقع، هذا لديه حرف واحد فقط، وهذا يعني أنه يجب أن يكون "أنا" في هذه الحالة، وجدنا خاصتنا الفريدة.

يمكنك أيضا أن تفعل الشيء نفسه بالنسبة للبكسلات التي ستكون بيضاء. لاحظ أن دلو (2،0) يحتوي على جميع الحروف باستثناء "L"، وهذا يعني أنه يمكن استخدامه كاختبار بيكسل أبيض. وبالمثل، (2،4) لا يحتوي على "أ".

يمكن التخلص من الدلاء التي تحتوي إما على جميع الأحرف أو أي من الحروف على الفور، لأن هذه البكسلات لا يمكن أن تساعد في تحديد مميزة فريدة (على سبيل المثال 1،1؛ 4،0؛ 0،1؛ 4،4).

يحصل الصعوبة عندما لا يكون لديك اختبار 1 بكسل للحرف، على سبيل المثال في حالة "O" و "B". دعنا نسير من خلال اختبار "O" ...

إنه موجود في الدلاء التالية:

// Bucket   Count   Letters
// 2,0      4       I, A, O, B
// 3,1      3          A, O, B
// 3,2      2          A, O
// 2,4      4       I,    O, B, L

بالإضافة إلى ذلك، لدينا أيضا عدد قليل من اختبارات بكسل بيضاء يمكن أن تساعد: (أنا فقط أدرج أولئك المفقودين على الأكثر 2). تم حساب العد المفقود ك (5 - bucket.count).

// Bucket   Missing Count   Missing Letters
// 1,0      2                  A, O
// 1,1      2               I,    O
// 2,2      2                     O,    L
// 3,4      2                     O, B

حتى الآن يمكننا أن نأخذ أقصر دلو بكسل أسود (3،2) ونرى أنه عندما نختبر (3،2) نعلم أنه إما "أ" أو "س". لذلك نحن بحاجة إلى طريقة سهلة لإخبار الفرق بين "A" و "O". يمكننا إما أن نبحث عن دلو بكسل أسود يحتوي على 'o' ولكن ليس "A" (على سبيل المثال 2،4) أو دلو بكسل أبيض يحتوي على "O" ولكن ليس "A" (مثل 1،1). يمكن استخدام أي من هذه المشترك مع (3،2) بكسل لتحديد الحرف "O" بشكل فريد مع اختبارات 2 فقط.

يبدو أن هذا مثل خوارزمية بسيطة عندما يكون هناك 5 أحرف، ولكن كيف أفعل هذا عندما يكون هناك 26 حرفا ومتداخلة بكثير بكثير بكسل؟ على سبيل المثال، دعنا نقول أنه بعد اختبار البكسل (3،2)، وجد 10 شخصيات مختلفة تحتوي على بكسل (وهذا كان أقل من جميع الدلاء). أحتاج الآن إلى إيجاد اختلافات من 9 أحرف أخرى بدلا من حرف واحد فقط. كيف يمكنني تحقيق هدفي المتمثل في الحصول على أقل قدر من الشيكات قدر الإمكان، والتأكد من أنني لا أقوم بتشغيل الاختبارات الخارجية؟

Answer 1

ليس لدي إجابة، ولكن هنا بعض الحدود في محلولك النهائي:

إذا كنت تريد مباشرة "استخدام X Pixels ككل مفتاح"، فستحتاج إلى الأقل ceiling(log2(number of characters)) بكسل. لن تكون قادرا على تكريس الرسائل مع أجزاء أقل. في حالتك، تحاول العثور على 5 بكسل تعادل العثور على 5 بكسل تقسيم الحروف إلى أقسام مستقلة. ربما ليس بهذه السهولة.

يمكنك أيضا استخدام Moron's (Heheh) اقتراح وبناء شجرة بناء على ترددات خطاب اللغة التي تقوم بمسحها مشابهة ل هوفمان الترميز. وبعد من شأنه أن يستغرق مساحة أكبر من 5 بت لكل حرف، ولكن من المحتمل أن تكون أصغر على افتراض أ توزيع القانون من استخدام الرسالة. أود أن أذهب مع هذا النهج لأنه يسمح لك بالبحث عن تقسيم معين لكل عقدة بدلا من البحث عن مجموعة من الأقسام.

Answer 2

يمكنك إنشاء شجرة.

اختر بكسل، وقسم الحروف إلى دلاءين، استنادا إلى البكسل بيضاء أو أسود. ثم اختيار بكسل الثاني، قم بتقسيم الدلاء إلى اثنين من الدلاء لكل بكسل وهلم جرا.

يمكنك محاولة تحسين عمق الشجرة عن طريق اختيار وحدات البكسل التي تعطي الدلاء المساواة تقريبا في الحجم.

إنشاء الشجرة خطوة واحدة مسبقا مرة واحدة. يجب ألا تضطر إلى القيام بذلك عدة مرات.

الآن عند الحصول على الأبجدية للمطابقة، اتبع الشجرة المستندة إلى مجموعة البكسل / لم يتم تعيين والحصول على رسالتكم.

Answer 3

ليس لدي خوارزمية لتعطيك الميزات الرئيسية، ولكن هنا بعض الأشياء التي قد تساعد.

أولا، لا تقلق كثيرا على البحث عن بكسل مميز لكل حرف لأنه، في المتوسط، والتحقق من ما إذا كان يجب ألا يستغرق مطابقات أحرف معينة مع Swath (5x5) من الصورة الثنائية أكثر من 5-7 يتحقق معرفة أن لا توجد مباراة. لماذا ا؟ احتمالا. ل 7 بكسل ثنائي، هناك 2 ** 7 = 128 إمكانيات مختلفة. هذا يعني وجود فرصة 1/128 <1٪ من الطابع المطابق حتى تصل إلى 7 بكسل. فقط تأكد من إيقاف المقارنات مباشرة عند العثور على عدم تطابق.

ثانيا، إذا كنت لا ترغب في القيام بجدول تجزئة، فقد تفكر في استخدام تري لتخزين جميع بيانات الشخصية الخاصة بك. سوف تستخدم ذاكرة أقل، وسوف تتحقق من كل الأحرف في وقت واحد. لن يكون الأمر سريعا دائما للبحث كجدول تجزئة، لكنك لن تضطر أيضا إلى تحويل إلى سلسلة. في كل عقدة في الشجرة، لا يمكن إلا أن يكون هناك فقط 2 أحفاد. على سبيل المثال، إذا كان لديك حرفين 2 × 2 (دعونا نسميهم A و B):

A   B
01  00
10  11

سيكون لك Trie سليل واحد فقط في العقدة الأولى - فقط إلى اليسار (الفرع 0). ننتقل إلى هذه العقدة التالية. لديها اثنين من النزولين، الفرع اليسرى (0) يؤدي إلى بقية B وفرع اليمين (1) يؤدي إلى بقية A. تحصل على الصورة. اسمحوا لي أن أعرف إذا كان هذا الجزء غير واضح.

Answer 4

لماذا لا تنظر فقط في الصورة كعدد صحيح 25 بت؟ قد تعمل INT INT 32 بت. على سبيل المثال، يمكن علاج الحرف "I" كعدد صحيح 14815374 في عشري لتعبيره الثنائي هو 011100010000100001000110110. إنها راحة لك لمقارنة صورتين مع العملية "==" كعدد صحيح

Answer 5

تتمثل إحدى الطرق في تحديد بكسل الأسود في نصف الحروف والأبيض تقريبا في المجموعة الأخرى. يمكن بعد ذلك استخدام هذا لتقسيم الحروف إلى مجموعتين، باستخدام خوارزمية نفس النصفين بشكل متكرر، حتى تصل إلى أحرف فردية.

إذا لم تتمكن من العثور على بكسل واحد ينقسم مجموعات إلى قسمين، فقد تضطر إلى الذهاب إلى مجموعة من اثنين أو أكثر من وحدات بكسل، ولكن نأمل أن تستخدم بكسل واحد جيدا بما فيه الكفاية.

للعثور على البكسل، ابدأ بمجموعة من الأعداد الصحيحة، بنفس حجم الحروف الخاصة بك، تهيئة جميع العناصر إلى 0، ثم زيادة العناصر إذا كان بكسل المقابل في حرف هو (يقول) أسود. تلك التي تهتم بها هي تلك الموجودة في نطاق (تقريبا) 10≤Sum ≤16 (على المستوى الأعلى، ستحتاج المستويات المنخفضة إلى استخدام حدود أخرى).

Answer 6

حسنا، لقد اكتشفت الحل.

يمكنك ببساطة استخدام البحث الأول في كل بكسل واحد مع كل مزيج بكسل آخر، حتى تجد مجموعة من الخصائص الفريدة للحرف. أثناء إجراء البحث الأول في العمق، تأكد من عدم بدء تشغيله في X = 0 و Y = 0 في كل مرة لأنك تريد فقط معالجة كل مجموعة مرة واحدة فقط، إذن ما تنتهي به الأمر هو زيادة قيم X و Y في كل منهما تكرار.

أنشأت كائن مساعد يحتوي على هذه الخصائص:

public Point LastPoint { get; set; }
public List<OcrChar> CharsWithSimilarProperties { get; set; }
public List<Point> BlackPixels { get; set; }
public List<Point> WhitePixels { get; set; }

بالنسبة لكل تكرار، إذا لم أستطع العثور على مميزة فريدة من نوعها (مثل جميع الحروف الأخرى لها بكسل هذا باللون الأسود، إلا أن هذه الرسالة لديها أبيض ... أو معكوس) أضيف جميع وحدات بكسل لاحقة إلى قائمة انتظار تتم معالجتها، عن طريق إنشاء مثيل لهذا الكائن أعلاه مع خصائص تعيين بشكل صحيح.

بعض رمز psuedo:

rootNode.LastPoint = new Point(-1, -1)
rootNode.CharsWithSimilarProperties = all letters in alphabet except for this one
queue.Add(rootNode)

while queue.HasNodes()
  for each pixel after node.LastPoint
    if node.IsBlackPixel(pixel) && node.CharsWithSimilarProperties.IsAlwaysWhite(pixel)
      node.BlackPixels.Add(pixel)
      return node.BlackPixels and node.WhitePixels

    if node.IsWhitePixel(pixel) && node.CharsWithSimilarProperties.IsAlwaysBlack(pixel)
      node.WhitePixels.Add(pixel)
      return node.BlackPixels and node.WhitePixels

    newNode = new Node();
    newNode.BlackPixels = node.BlackPixels.Copy();
    newNode.WhitePixels = node.WhitePixels.Copy();
    newNode.LastPoint = pixel
    if node.IsBlackPixel(pixel)
      newNode.BlackPixels.Add(pixel)
      newNode.CharsWithSimilarProperties = list of chars from node.CharsWithSimilarProperties that also had this pixel as black
    else
      newNode.WhitePixels.Add(pixel)
      newNode.CharsWithSimilarProperties = list of chars from node.CharsWithSimilarProperties that also had this pixel as white
    queue.Add(newNode)

لتحديد ما إذا كان "node.charswithsimilarproperites.isalwayswhite ()" أو "isalwaysblack ()، يمكنك إنشاء مركبة مركبة في كل تكرار في قائمة الانتظار:

  for each pixel after node.LastPoint
    for each char in node.CharsWithSimilarProperties
      if char.IsBlackPixel(pixel)
        compositeMap[pixel].Add(char)

قبل القيام بكل هذا، قمت أيضا بمعالجة الأبجدية بأكملها للعثور على بكسلات بيضاء دائما أو سوداء دائما، لأن هذه لا يمكن استخدامها أبدا. أضفتهم إلى List<Point> ignoredPixels, ، وفي كل مرة أتوج بها من البكسل، أنا دائما استخدام if (ignoredPixels[x, y]) continue;.

هذا يعمل تماما وهو سريع حقا. على الرغم من أن تضع في اعتبارك أن هذا الجزء من حلي لا يحتاج إلى أن يكون سريعا على الإطلاق لأنه تحسين لمرة واحدة يساعدني في وقت لاحق. في حالات الاختبار الخاصة بي بحد أقصى 8 حصري لكل مجموعة لكل "الأبجدية"، فإنها عادة ما تنتج خصائص واحدة أو اثنين لكل حرف. لم أكن بعد تشغيلها على مجموعة كاملة من 26 حرفا.

Answer 7

أنا ذاهب إلى أسفل مسار مماثل يحاول اختراع خوارزمية من شأنها أن تعطيني عدد أقل من الاختبارات التي يمكنني استخدامها لتتناسب مع صورة إلى واحد رأيته سابقا. تطبيقي هو OCR ولكن في مجال محدود من التعرف على صورة من مجموعة ثابتة من الصور بأسرع وقت ممكن.

افتراضي الأساسي (الذي أظن أنه هو نفسه لك، أو كان هو نفسه) هو أنه إذا استطعنا تحديد بكسل فريد واحد (حيث يتم تعريف البكسل كنقطة داخل الصورة بالإضافة إلى اللون)، فقد وجدنا المثالي ( أسرع) اختبار لتلك الصورة. في حالتك تريد أن تجد الحروف.

إذا لم نتمكن من العثور على صورة واحدة من هذه البكسل، فإننا (مضيء) ابحث عن بكسلين من نوعها فريدة من نوعها. أو ثلاثة. وهلم جرا، حتى يكون لدينا اختبار ضئيل لكل من الصور.

يجب أن أشير إلى أن لدي شعور قوي أنه في مجال خاص بي، سأكون قادرا على العثور على مثل هذه البكسلات الفريدة. قد لا يكون الأمر نفسه بالنسبة لتطبيقك حيث يبدو أن لديك الكثير من "التداخل".

بعد النظر في التعليقات في هذا السؤال الآخر (حيث بدأت للتو في الحصول على شعور لهذه المشكلة) وتعليقات هنا أعتقد أنني قد أكون قد وصلت إلى خوارزمية عملية.

هنا ما لدي حتى الآن. تتم كتابة الطريقة التي وصفتها أدناه في الملخص ولكن في طلبي كل "اختبار" هو بكسل تم تحديد بكسل بنقطة بالإضافة إلى اللون، وتمثل "النتيجة" هوية الصورة. تحديد هذه الصور هو هدفي النهائي.

النظر في الاختبارات التالية مرقمة T1 إلى T4.

• T1.: ABC.
• T2.: ب
• T3.: ACD
• T4.: ميلادي

يمكن تفسير قائمة الاختبارات هذه على النحو التالي؛

• إذا اختبار T1. صحيح أننا نستنتج أن لدينا نتيجة ل A أو B أو C.
• إذا اختبار T2. صحيح أننا نستنتج أن لدينا نتيجة B.
• إذا اختبار T3. صحيح أننا نستنتج أن لدينا نتيجة ل A أو C أو D.
• إذا اختبار T4. صحيح أننا نستنتج أن لدينا نتيجة ل A أو D.

لكل نتيجة فردية A، B، C، D، نريد إيجاد مزيج من الاختبارات (من الناحية المثالية اختبار واحد فقط) سيسمح لنا باختبار نتيجة لا لبس فيها.

تطبيق الحدس ومع القليل من التحديق على الشاشة، يمكننا أن تلمس طريقنا إلى الترتيب التالي للاختبارات.

بالنسبة إلى A يمكننا اختبار مزيج من T4 (إما A أو D) و T1 (ولكن ليس د)

ب سهل لأن هناك اختبار T2 الذي يعطي النتيجة ب ولا شيء آخر.

C أكثر صعوبة، ولكن في النهاية يمكننا أن نرى أن مزيج من T3 (A أو C أو D) وليس T4 (وليس A وليس D) يعطي النتيجة المرجوة.

وبالمثل، يمكن العثور على D مع مزيج من T4 و (وليس T1).

باختصار

A <- T4 && T1
B <- T2
C <- T3 && ¬T4
D <- T4 && ¬T1

(أين <- يجب أن تقرأ كما "يمكن العثور عليها إذا كانت الاختبارات التالية تقيم إلى True ')

الحدس والحدوى على ما يرام، ولكن ربما لن نحصل على هذه التقنيات المدمجة في اللغة حتى لا تقل عن C # 5.0، لذلك هنا محاولة لإضفاء الطابع الرسمي على طريقة التنفيذ بلغات أقل.

للعثور على نتيجة R,

1. العثور على الاختبار Tr هذا يعطي النتيجة المرجوة R وأقل النتائج غير المرغوب فيها (مثالية لا توجد بها
2. إذا كان الاختبار يعطي النتيجة R ولا شيء آخر انتهينا. يمكننا أن نتطابق مع R أين Tr صحيح.
3. لكل نتيجة غير مرغوب فيها X في الاختبار Tr;
   • (أ) ابحث عن أقصر اختبار Tn ذلك يعطي R لكن لا X. وبعد إذا وجدنا مثل هذا الاختبار، فيمكننا مطابقته بعد ذلك R أين (T && Tn)
   • (ب) إذا لم يكن هناك حالة تطابق اختبار (أ) ثم ابحث عن أقصر الاختبار Tx وهذا يشمل X ولكن لا يشمل R. وبعد (مثل هذا الاختبار من شأنه القضاء X نتيجة من اختبار Tr). يمكننا بعد ذلك اختبار R أين (T && ¬Tx)

الآن سأحاول اتباع هذه القواعد لكل من النتائج المرجوة، A، B، C، D.

فيما يلي الاختبارات مرة أخرى للرجوع إليها؛

• T1.: ABC.
• T2.: ب
• T3.: ACD
• T4.: ميلادي

ل

وفقا للمادة (1) نبدأ مع T4 لأنها أبسط اختبار يعطي النتيجة A. ولكنه يعطي أيضا النتيجة "D" وهو نتيجة غير مرغوب فيها. وفقا للمادة (3) يمكننا استخدام اختبار T1 لأنه يشمل "A" ولكن لا يشمل "D".

لذلك يمكننا اختبار مع

A <- T4 && T1

ل B.

للعثور على 'B' نحن نجد بسرعة اختبار T2 وهذا هو أقصر اختبار ل 'B' وبالتالي فإنه يعطي النتيجة فقط "B" انتهينا.

B <- T2

ل C.

للعثور على "C" نبدأ مع T1 و T3. نظرا لأن نتائج هذه الاختبارات قصيرة بنفس القدر، فاخترنا بشكل تعسفي T1 كنقطة انطلاق.

الآن وفقا ل (3A) نحتاج إلى إيجاد اختبار يتضمن "C" ولكن ليس "A". نظرا لعدم أي اختبار يرضي هذا الحالة لا يمكننا استخدام T1 كأول اختبار. T3 لديه نفس المشكلة.

عدم القدرة على إيجاد اختبار يرضي (3A) نبحث الآن عن اختبار يرضي الحالة (3B). نحن نبحث عن اختبار يعطي "A" ولكن ليس "C". يمكننا أن نرى أن اختبار T4 يرضي هذا الشرط، لذلك يمكننا اختبار ج

C <- T1 && ¬T4

معقل

للعثور على د أن نبدأ مع T4. يتضمن T4 النتيجة غير المرغوب فيها أ. لا توجد اختبارات أخرى تعطي النتيجة د ولكن لا ننظر إلى اختبار يعطي اختبارا ولكن ليس D. اختبار T1 يرضي هذا الشرط بحيث يمكننا اختبار D

D <= T4 && ¬T1

هذه النتائج جيدة لكنني لا أعتقد أنني قمت بتصحيح هذه الخوارزمية بما يكفي للحصول على ثقة بنسبة 100٪. سأفكر في الأمر أكثر قليلا وربما كود بعض الاختبارات لمعرفة كيفية حملها. لسوء الحظ، فإن الخوارزمية تعقيدا بما يكفي بحيث ستستغرق الأمر أكثر من بضع دقائق لتنفيذها بعناية. قد يكون الأمر قبل أيام من اختتام أي شيء آخر.

تحديث

لقد وجدت أنه من الأمثل البحث في وقت واحد عن الاختبارات التي ترضي (أ) أو (ب) بدلا من البحث عن (أ) ثم (ب). إذا نظرنا أولا في (أ)، فقد نحصل على قائمة طويلة من الاختبارات عندما يكون لدينا قائمة أقصر من خلال السماح باختبارات بعض (ب).