algorithm एल्गोरिदम: सफेद भागों का उपयोग करके एन भागों में एक स्ट्रिंग को विभाजित करें ताकि सभी भागों में लगभग समान लंबाई हो




string split (6)

मैं एक एल्गोरिथ्म की तलाश कर रहा हूं जो एक स्ट्रिंग लेता है और इसे निश्चित भागों में विभाजित करता है। इन हिस्सों में पूरे शब्दों को सम्मिलित किया जाता है (इसलिए स्ट्रिप्स को विभाजित करने के लिए सफेद स्थानों का उपयोग किया जाता है) और भागों लगभग समान लंबाई के होंगे, या सबसे लंबे समय तक संभव भागों होते हैं।

मुझे पता है कि यह ऐसा कार्य नहीं करना कठिन है, जो कि मैं क्या कर सकता हूं लेकिन मुझे आश्चर्य है कि क्या उस उद्देश्य के लिए एक अच्छी तरह से सिद्ध और तेज एल्गोरिथ्म है?

संपादित करें: मेरे प्रश्न को स्पष्ट करने के लिए मैं आपको उस समस्या का वर्णन करूँगा जो मैं हल करने की कोशिश कर रहा हूं।

मैं एक निश्चित चौड़ाई के साथ चित्र उत्पन्न करता हूँ। इन छवियों में मैं पीडीए में जीडी और फ़्रीटाइप का इस्तेमाल करते हुए उपयोगकर्ता नाम लिखता हूं। चूंकि मुझे एक निश्चित चौड़ाई है इसलिए मैं नामों को 2 या 3 पंक्तियों में विभाजित करना चाहता हूं यदि वे एक में फिट नहीं होते हैं

जितना संभव हो सके उतना स्थान भरने के लिए मैं नामों को ऐसे तरीके से विभाजित करना चाहता हूं कि प्रत्येक पंक्ति में यथासंभव अधिक से अधिक शब्द हों। इसके साथ मेरा मतलब है कि प्रत्येक पंक्ति की लंबाई पूरे टेक्स्ट ब्लॉक की औसत रेखा की लंबाई के पास रखने के लिए एक पंक्ति में जितनी अधिक आवश्यक होनी चाहिए। इसलिए यदि एक लंबे शब्द और दो छोटे शब्द हैं तो दो छोटे शब्दों को एक पंक्ति पर खड़ा होना चाहिए, अगर यह समान लंबाई के बारे में सभी पंक्तियाँ बनाता है

(फिर मैं 1, 2 या 3 पंक्तियों का उपयोग करके पाठ ब्लॉक की चौड़ाई की गणना करता हूं और यदि यह मेरी छवि में फिट होता है तो मैं इसे प्रस्तुत करता हूँ। बस अगर 3 लाइनें होती हैं और यह फिट नहीं होगा, तब तक मैं फ़ॉन्ट आकार कम नहीं करूँगा जब तक कि सब कुछ ठीक न हो।

उदाहरण: This is a long text है, जैसा कि कुछ दिखाना चाहिए:

This is a
long text

या:

This is
a long
text

लेकिन नहीं:

This
is a long
text

और भी नहीं:

This is a long
text

आशा है कि मैं स्पष्ट कर सकता हूं कि मैं क्या देख रहा हूं।



ब्रायन के उत्तर के बाद, मैंने उनके कोड का जावास्क्रिप्ट संस्करण बनाया: http://jsfiddle.net/gmoz22/CPGY2/

// Input text
var txt = "This is a really long string that should be broken up onto lines of about the same number of characters.";

// Number of lines
var numLines = 3;

/* Do it, result comes as an array: */
var aResult = splitLinesByClosestWhitespace(txt, numLines);

/* Output result: */
if (aResult) 
{
    for (var x = 1; x<=numLines; x++) 
        document.write( "Line "+x+": " + aResult[x] + "<br>" );

} else {
    document.write("Not enough spaces to generate the lines!");
}


/**********************/
// Original algorithm by http://.com/questions/2381525/algorithm-split-a-string-into-n-parts-using-whitespaces-so-all-parts-have-nearl/2381772#2381772, rewritten for JavaScript by Steve Oziel


/**
 * Trims a string for older browsers
 * Used only if trim() if it is not already available on the Prototype-Object
 * since overriding it is a huge performance hit (generally recommended when extending Native Objects)
 */
if (!String.prototype.trim) 
{
    String.prototype.trim = function(){return this.replace(/^\s+|\s+$/g, '');};
}


/**
 * Splits a string into multiple lines of the closest possible same length, 
 * using the closest whitespaces
 * @param {string} txt  String to split
 * @param {integer} numLines    Number of lines
 * @returns {Array}
 */
function splitLinesByClosestWhitespace(txt, numLines) 
{
    var p           = parseInt(txt.length / numLines);
    var aTxtIndx    = [];
    var aTxt        = [];

    // Check we have enough whitespaces to generate the number of lines
   var wsCount = txt.split(" ").length - 1;
   if (wsCount<numLines)
       return false;

    // Get the indexes
    for (var x=1;  x<=numLines; x++) 
    {
        aTxtIndx[x] = FindClosestWordIndex(txt, p * (x-1) );
    }
    // Do the split
    for (var x=1;  x<=numLines; x++) 
    {
        if (x != numLines)
            aTxt[x] = txt.slice(aTxtIndx[x], aTxtIndx[x+1]).trim();
        else 
            aTxt[x] = txt.slice(aTxtIndx[x]).trim();
    }

    return aTxt;
}

/**
 * Finds the closest word to a string index
 * @param {string} s    String to search
 * @param {integer} startIndex Index at which to find the closest word
 * @returns {integer}
 */
function FindClosestWordIndex(s, startIndex) 
{
    var wordAfterIndex = 0;
    var wordBeforeIndex = 0;
    for (var i = startIndex; i < s.length; i++)
    {
        if (s[i] == ' ')
        {
            wordAfterIndex = i;
            break;
        }
    }
    for (var i = startIndex; i >= 0; i--)
    {
        if (s[i] == ' ')
        {
            wordBeforeIndex = i;
            break;
        }
    }

    if (wordAfterIndex - startIndex <= startIndex - wordBeforeIndex)
        return wordAfterIndex;
    else
        return wordBeforeIndex;
}

यह ठीक काम करता है जब वांछित लाइनों की संख्या भी सफेद स्थानों की संख्या के करीब नहीं होती है उदाहरण के लिए मैंने दिया, वहां 1 9 गोलाएं हैं और जब आप इसे 17, 18 या 1 9 लाइनों में तोड़ने के लिए कहें तो यह बग शुरू हो जाएगा। संपादन का स्वागत है!


मुझे साबित करने के बारे में पता नहीं है, लेकिन ऐसा लगता है कि सबसे सरल और सबसे कुशल समाधान N द्वारा स्ट्रिंग की लंबाई को विभाजित करने के लिए होगा, तो विभाजित स्थानों के लिए सबसे निकटतम सफेद स्थान ढूंढें (आप आगे और पीछे दोनों खोजना चाहते हैं )।

नीचे कोड काम करने लगता है हालांकि इसमें बहुत सारी त्रुटि स्थितियां हैं, जो इसे संभाल नहीं पाती हैं। ऐसा लगता है कि यह ओ (एन) में चलेगा, जहां एन तार की संख्या है जिसे आप चाहते हैं।

class Program
{
    static void Main(string[] args)
    {
        var s = "This is a string for testing purposes. It will be split into 3 parts";
        var p = s.Length / 3;
        var w1 = 0;
        var w2 = FindClosestWordIndex(s, p);
        var w3 = FindClosestWordIndex(s, p * 2);
        Console.WriteLine(string.Format("1: {0}", s.Substring(w1, w2 - w1).Trim()));
        Console.WriteLine(string.Format("2: {0}", s.Substring(w2, w3 - w2).Trim()));
        Console.WriteLine(string.Format("3: {0}", s.Substring(w3).Trim()));
        Console.ReadKey();
    }

    public static int FindClosestWordIndex(string s, int startIndex)
    {
        int wordAfterIndex = -1;
        int wordBeforeIndex = -1;
        for (int i = startIndex; i < s.Length; i++)
        {
            if (s[i] == ' ')
            {
                wordAfterIndex = i;
                break;
            }
        }
        for (int i = startIndex; i >= 0; i--)
        {
            if (s[i] == ' ')
            {
                wordBeforeIndex = i;
                break;
            }
        }

        if (wordAfterIndex - startIndex <= startIndex - wordBeforeIndex)
            return wordAfterIndex;
        else
            return wordBeforeIndex;
    }
}

इसके लिए आउटपुट है:

1: This is a string for
2: testing purposes. It will
3: be split into 3 parts


जिस तरह से शब्द-लपेटो आम तौर पर लागू किया जाता है वह एक पंक्ति पर जितनी संभव हो सके उतने शब्द रखे, और अगले कमरे में तोड़ दें जब कोई और कमरा न हो यह निश्चित रूप से मानता है, कि आपके पास अधिकतम चौड़ाई दिमाग है।

आप किस एल्गोरिथम का उपयोग करते हैं, यह ध्यान रखें कि जब तक आप निश्चित चौड़ाई वाले फ़ॉन्ट के साथ काम नहीं कर रहे हैं, आप शब्द की भौतिक चौड़ाई के साथ काम करना चाहते हैं, न कि अक्षरों की संख्या






split